Leetcode挑戰: Day08 majority element

leetcode

為了加強自己的程式能力,因此開始記錄每天刷leetcode的解法+說明,會用RubypythonJavaScript三個語言來解題,今天是第八天,讓我們開始吧!

題目來源:leetcode

在讀題目的時候,發現有一個小細節,題目寫要找出出現次數大於[n/2]的數字,且假定這個數字一定存在Array中。那也就代表,只要找出最常出現的數就可以了,因為陣列中只要其中一個數出現的數量大於[n/2],剩下的數出現次數就不會大於[n/2],可以想像成,西瓜被挖走一半多一點,剩下的西瓜再怎麼分都沒辦法大於一半。

所以這題只要找出,出現次數最多的數字即可!讓我們開始解題吧~

Ruby

1
2
3
def majority_element(nums)
nums.tally.max_by {|key, value| value }[0]
end

這裡使用了tally

在Ruby API的解釋為:

1
2
3
4
Enumerable#tally
Returns a hash containing the counts of equal elements:
Each key is an element of self.
Each value is the number elements equal to that key.

意思就是建立一個hash,key是self,value是出現的次數,簡單的範例:

1
2
3
result = %w[a b c b c a c b].tally
puts result
# => {"a"=>2, "b"=>3, "c"=>3}

建立了hash之後,即可以使用max_bymax_bymax_by允許輸入值為{},會返還{}內最大的值,因為返還的會是Array,來看一下範例:

1
2
3
result = {foo: 1, bar: 10, baz: 8}.max_by {|key, value| value }
puts result
#[:bar, 10]

如果只要取出key呢?可以使用[0]來取出Array的第一個數,也是Array內最常出現的key:

1
2
3
result = {foo: 1, bar: 10, baz: 8}.max_by {|key, value| value }[0]
puts result
#10

Python

1
2
3
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return Counter(nums).most_common(1)[0][0]

在python計算數量可以使用Counter()物件,來看看範例:

1
2
3
4
5
6
7
from collections import Counter
words = ['red', 'blue', 'red', 'green', 'blue', 'blue']
cnt = Counter()
cnt.update(words)

print(cnt)
#Counter({'blue': 3, 'red': 2, 'green': 1})

接著可以使用.most_common(1)[0][0](1)代表取出第一個結果,這時輸出的值會是[(3, 2)],因此還必須要使用[0][0]代表取出第一組Array的第一個數才會得到解答!

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function majorityElement(nums) {
let count = 0;
let majority;

for (const num of nums) {
if (count === 0) {
majority = num;
}

count += (num === majority) ? 1 : -1;
}

return majority;
}

JS我採用的是摩爾投票法,消除不同元素之間的票數,最終保留的就是可能的主要元素。

一開始先把count設定為0,如果接下來遇到的數字相同count + 1,不同count - 1,如果count又變回 0(代表刪掉一樣數量的a & b),這時就會更改majority = num,最後殘存活下來的就是majority了!

Comments