LeetCode： Majority Element

Question

在一個有 n 個元素的集合(Array)裡，要找到出現次數最多的元素 majority element (定義為出現次數要超過⌊ n/2 ⌋)。

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]

Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]

Output: 2

@param {Integer[]} nums

@return {Integer}

---

Solution

首先賦予初始值 0 給ㄧ個新的 Hash，並且命名為 counter。 接著將傳進來的 num (Array 型態) 以 each 方法將 num 集合內的每個元素轉出。 這些元素都會成為 counter(Hash 型態) 中的 Key，而對應的 value 會是以 key 出現的次數來計算。

當 each 方法跑完之後，也代表完成紀錄每個字母出現的次數了。 可使用 max 方法要找出在 Hash 中，value 的最大值。 最後再以 Hash 所提供的 select 方法可找出擁有最大值 value 的 key，也就是出現次數最多的元素 majority element。

def majority_element(nums)
  counter = Hash.new(0)
  nums.each do |num|
    counter[num] += 1
    counter
  end
  max_count = (counter.values).max
  counter.select{|k, v| v == max_count}.keys.first
end