Ruby幼幼班--Majority Element

偶尔分享一下新歌...

Majority Element

题目连结:https://leetcode.com/problems/majority-element/
题目重点:The majority element is the element that appears more than ⌊n / 2⌋ times.
这句可以导出另一种解法。
整理:

# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
  
end

p majority_element([3,2,3]) #=>3
p majority_element([[2,2,1,1,1,2,2]]) #=>2

依照前一题的分享,已经知道tally用法

2.7.3 :083 > [2,2,1,1,1,2,2].tally
 => {2=>4, 1=>3} 
#那就找出value中最大值的Key就可以了。(4与3,最大的那个的key)

英文不好,中文也不好...

查到hash也可以用max_by。
https://stackoverflow.com/questions/6040494/how-to-find-the-key-of-the-largest-value-hash

max_by用在Hash还蛮需要注意带什麽值进去处理的。

#Array 手册上的示范。
2.7.3 :009 > ["abcdefg", "ascv", "zzz"].max_by {|string|string.length}
 => "abcdefg" 
2.7.3 :010 > ["abcdefg", "ascv", "zzz"].max_by(2) {|string|string.length}
 => ["abcdefg", "ascv"] 
 
#Hash 
2.7.3 :011 > {4=>4, 1=>3, 3=>5}.max_by{|key, value|key}
 => [4, 4] 
2.7.3 :012 > {4=>4, 1=>3, 3=>5}.max_by{|key, value|value}
 => [3, 5]
 
#ans
2.7.3 :013 > [2,2,1,1,1,2,2].tally
 => {2=>4, 1=>3} 
2.7.3 :014 > [2,2,1,1,1,2,2].tally.max_by{|key, value|value}
 => [2, 4] 
2.7.3 :015 > [2,2,1,1,1,2,2].tally.max_by{|key, value|value}.first
 => 2 

整理後

def majority_element(nums)
  nums.tally.max_by{|key, value| value}.first
end

数学解法(统计学?)

The majority element is the element that appears more than ⌊n / 2⌋ times.就是指"众数"。

如果真的无法理解,常态分布时,众数会与中位数重合,那就先观察吧。

2.7.3 :061 > [3,2,3].sort.map.with_index {|num, index|[index, num]}.to_h
 => {0=>2, 1=>3, 2=>3} 
2.7.3 :062 > [1, 1, 1, 2, 2, 2, 2].sort.map.with_index {|num, index|[index, num]}.to_h
 => {0=>1, 1=>1, 2=>1, 3=>2, 4=>2, 5=>2, 6=>2} 

解法

def majority_element(nums)
  nums.sort[nums.size/2]
end

补充提醒:

#都Integer时," / "号,不带小数点
2.7.3 :063 > 7/2
 => 3
#除非Float
2.7.3 :067 > 7/2.0
 => 3.5 
2.7.3 :068 > 7.0/2
 => 3.5 
#然後如果[]里带Float,只看整数部分。
2.7.3 :069 > [1, 2, 3][1.4]
 => 2 
2.7.3 :070 > [1, 2, 3][1.8]
 => 2 

打了高端,解题也不会变厉害的,还是要乖乖练习T_T...