Viiisit [LeetCode] - 169. Majority Element

keep learning, keep coding!

Problem - Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

翻譯蒟蒻

給定一個長度為 n 的整數陣列 nums，找出其中的主要元素（在陣列中出現次數超過一半以上的元素）。

• Example 1:

  Input: nums = [3,2,3]
  Output: 3

• Example 2:

  Input: nums = [2,2,1,1,1,2,2]
  Output: 2

---

Solution - JavaScript

Solution 1:
(Runtime - 51ms)

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  let counter = {}
  for (let i = 0; i < nums.length; i++) {
    let num = nums[i]

    // 如果 num 不存在於 counter，就給他初始值 1
    if (!counter[num]) {
      counter[num] = 1
    } else {
      counter[num]++
    }

    // 最後以如果在 counter 裡的數字次數超過陣列長度除以 2 的話，意即為主要出現最多次的元素，則返回該 num
    if (counter[num] > nums.length / 2) {
      return num;
    }
  }
};

• Solution 1 使用 counter 來記錄每個不同的數字在數組中出現的次數。對於每個數字我都檢查 counter 中是否已經存在該數字的計數，如果不存在，就初始化為 1，如果存在，就將計數增加。然後，檢查每個數字的計數是否超過了數組長度的一半，如果是，則返回該數字。

Solution 2:
(Runtime - 47ms)

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  let score = 0
  let count = 0
  for (i = 0; i < nums.length; i++) {
      if (count == 0) {
          count++;
          score = nums[i]
      } else if (score == nums[i]) {
          count++;
      } else {
          count--;
      }
  }
  return score;
};

• Solution 2 使用一種算法，稱為 Boyer-Moore 投票算法。通過兩個變數，score 和 count 來計算。遍歷 nums 陣列，對於每個數字，如果 count 等於 0，就將 score 設置為當前數字，然後增加 count。如果 count 不等於 0，並且當前數字等於 score，則增加 count；如果不等於 score，則減少 count。最終，score 中存儲的數字就是主要元素。

Solution 1 使用物件來存儲計數，會需要更多的空間，並且要額外的迴圈遍歷。
Solution 2 使用更少的空間（只需要兩個變數），並且只需遍歷一次 nums，因此在某些情況下可能更高效。

Solution - Ruby

Solution 1:
(Runtime - 81ms)

def majority_element(nums)
  counter = {}

  nums.each do |num|
    if counter[num].nil?
      counter[num] = 1
    else 
      counter[num] += 1
    end

    if counter[num] > nums.length / 2
      return num
    end
  end
    
end

Solution 2:
(Runtime - 61ms)

def majority_element(nums)
  score = 0
  count = 0

  nums.each do |num|
    if count == 0
      count += 1
      score = num
    elsif score == num
      count +=  1
    else
      count -= 1
    end
  end

  score
end

LeetCode 傳送門 - Majority Element