169. Majority Element

解題程式碼

var majorityElement = function (nums) {
  let majority = 0;
  let majorCounter = 0;

  nums.forEach((num) => {
    if (majorCounter === 0) majority = num;

    if (majority === num) {
      majorCounter++;
    } else {
      majorCounter--;
    }
  });

  return majority;
};

解題思路、演算法

這題用 hash map 解當然沒有問題，但無法達到題目 follow-up 的要求，因為宣告一個 new Map() 去計算字元就會消耗 O(n)。

Follow-up: Could you solve the problem in linear time and in O(1) space?

參考網路文章後，了解到會使用到 Moore majority vote algorithm(摩爾投票演算法)，題目中的 The majority element is the element that appears more than ⌊n / 2⌋ times. 很重要，意思是說 input 的陣列的最多數一定會超過陣列總元素的一半，是使用到這個演算法的條件。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(1)

參考資料

LeetCode: 169-Majority Element 解題紀錄

75. Sort Colors

解題程式碼

var sortColors = function(nums) {
    let l = 0;
    let i = 0;
    let r = nums.length - 1;

    const swap = (i, j) => {
      const temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
    }

    while (i <= r) {
      if (nums[i] === 0) {
        swap(l, i);
        l++;
        i++;
      } else if (nums[i] === 2) {
        swap(r, i);
        r--;
        // 這種情況，會有可能和右邊的 0、1、2 作交換
        // [0, 1, 2, 1, 0, 2]
        //     l  i     r
        // 變成以下這樣，但 i 不能往後，不然 0, 1, 0 的順序就被送出到最終結果了
        // [0, 1, 0, 1, 2, 2]
        //     l  i  r   
        // 所以這邊 i 不加一
      } else {
        i++;
      }
    }
    return nums;
};

解題思路、演算法

這題可以有兩種解法，先將整個 input 陣列遍歷過一次，然後去計算 0、1、2 各出現幾次，然後再遍歷一次原本陣列，逐一用計算出的 0、1、2 個數去取代原本陣列的元素。

另一個方法是如上面的範例程式碼，用 two pointer 代表陣列的開頭和結尾，從頭開始遍歷陣列，碰到 0 就把該元素移到陣列的前面，left point 的索引位置，碰到 2 就把該元素移到陣列的後面，right point 的索引位置，這樣 1 就會逐漸集中在中間。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(1)

參考資料

Sort Colors - Quicksort Partition - Leetcode 75 - Python

[Leetcode-19/30][Sort] #75 Sort Colors

217. Contains Duplicate

解題程式碼

var containsDuplicate = function (nums) {
  return nums.length !== [...new Set(nums)].length;
};

解題思路、演算法

解法的時間、空間複雜度

時間複雜度: O(1)
空間複雜度: O(n)

參考資料