偶爾分享一下新歌...
題目連結: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
#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
如果真的無法理解,常態分佈時,眾數會與中位數重合,那就先觀察吧。
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...