iT邦幫忙

0

Ruby幼幼班--Majority Element

  • 分享至 

  • xImage
  •  

Yes

偶爾分享一下新歌...


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...


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言