LeetCode Js-169. Majority Element

    AllenLi
    LeetCode Js-Array

    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.

    給予一個陣列 nums 且長度為 n，回傳多數的元素。
多數的元素是一個有出現 n / 2以上次數的元素。
你可以假設多數的元素一直都存在陣列中，也就是找出符合次數為長度除以 2 的元素。

    Example 1:

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

    Example 2:

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

    Solution:
    1. 如 nums 中只有一個元素時，回傳該元素的值。
    2. 宣告一個 box 物件。
    3. 進行 nums.length 長度的迴圈。
    4. 運用物件{}的特性，如果 box[i] 中沒有對應的物件，則顯示undefined，而 !undefined 為 false 轉為 true，執行對應物件次數為 {‘i’: 1}
    5-1. 如有 box[i] 存在物件中，則顯示次數，而 !1 的相反為 true 轉為 false，執行對應物件++ 為 {‘i’: 1 + 1}
    5-2. 如果該物件的次數大於 nums陣列的長度/2，則返回該數值。

    Code 1: BigO(n)

    var majorityElement = function(nums) {
  if (nums.length === 1) return nums[0]

  let box = {}

  for (let i = 0; i < nums.length; i++) {
    
    if (!box[nums[i]]) {
      box[nums[i]] = 1
    } else {
      box[nums[i]]++

      if (box[nums[i]] >= nums.length / 2) {
        return nums[i]
      }
    }
  }
};

    FlowChart:
    Example 1

    Input: nums = [3,2,3]
nums.length = 3

step.1
i = 0
box = {}
!box[nums[0]] => !box[3] => !undefined = true
box[nums[0]] = 1 //{'3': 1}

i = 1
box = {'3': 1}
!box[nums[1]] => !box[2] => !undefined = true
box[nums[1]] = 1//{ '2': 1, '3': 1 }

i = 2
box = {'2': 1, '3': 1}
!box[nums[2]] => !box[3] => !1 => false
box[nums[2]]++ => {'2': 1, '3': 2}
(box[nums[2]] >= nums.length / 2) //{'3'} 2 >= (3/2)=> 2 >= 1.5
return nums[2] //3

    Example 2

    Input: nums = [2,2,1,1,1,2,2]
nums.length = 7

step.1
i = 0
box = {}
!box[nums[0]] => !box[2] => !undefined = true
box[num[0]] = 1 //{'2': 1}

i = 1
box = {'2': 1}
!box[nums[1]] => !box[2] => !1 => false
box[nums[1]]++ => {'2': 2}
(box[nums[1]] >= nums.length / 2) //{'2'} 2 <= (7/2)=> 2 <= 3.5 loop

i = 2
box = {'2': 2}
!box[nums[2]] => !box[1] => undefined
box[num[2]] = 1 //{'1': 1, '2': 2}

i = 3
box = {'1': 1, '2': 2}
!box[nums[3]] => !box[1] => !1 => false
box[nums[3]]++ => {'1': 2, '2': 2}
(box[nums[3]] >= nums.length / 2) //{'1'} 2 <= (7/2)=> 2 <= 3.5 loop

i = 4
box = {'1': 2, '2': 2}
!box[nums[4]] => !box[1] => !2 => false
box[nums[4]]++ => {'1': 3, '2': 2}
(box[nums[4]] >= nums.length / 2) //{'1'} 3 <= (7/2)=> 3 <= 3.5 loop

i = 5
box = {'1': 3, '2': 2}
!box[nums[5]] => !box[2] => !2 => false
box[nums[5]]++ => {'1': 3, '2': 3}
(box[nums[5]] >= nums.length / 2) //{'2'} 3 <= (7/2)=> 3 <= 3.5 loop

i = 6
box = {'1': 3, '2': 3}
!box[nums[6]] => !box[2] => !3 => false
box[nums[6]]++ => {'1': 3, '2': 4}
(box[nums[6]] >= nums.length / 2) //{'2'} 4 >= (7/2)=> 4 >= 3.5
return nums[6] //2

    Code 2: Boyer–Moore majority vote algorithm BigO(n)

    var majorityElement = function(nums) {
    if (nums.length === 1) return nums[0];
    
    let target = 0, counter = 0

    for (const num of nums) {
        if (counter === 0) {
            target = num
            counter++
        } else if (target === num) {
            counter++
        } else {
            counter--
        }
    }
    return target;
};

    Code 3: Boyer–Moore majority vote algorithm BigO(n)

    var majorityElement = function(nums) {
    if (nums.length === 1) return nums[0];
    
    let target = 0, counter = 0

    for (const num of nums) {
        if (counter === 0) {
            target = num
        }
        counter += num === target ? 1 : -1
    }
    return target;
};

    Code 4: HashTable BigO(m + n)

    var majorityElement = function(nums) {
    if (nums.length === 1) return nums[0];

    let hashTable = {}

    for (let i = 0; i < nums.length; i++) {
        hashTable[nums[i]] = (hashTable[nums[i]] || 0) + 1
    }

    for (let num in hashTable) {
        if (hashTable[num] >= nums.length / 2) return num;
    }
};

    Related Posts