# 229 Majority Element II

記得先想 Edge Case

LeetCode 169 的延伸題

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

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

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

如何解

第一個想法就是把數字存進 obj 裡，然後哪一個 > 1/3 次就會丟進結果，這樣 Big O(n) 解決

var majorityElement = function(nums) {
    let obj = {};
    let len = nums.length;
    let judge = len/3;
    let result = []

    for(let i = 0; i<len; i++){
      if(obj[ nums[i] ]) {
        // if( count > judge)
        if(obj[ nums[i] ] + 1 > judge){
          result.push( nums[i] )
        }else {
          obj[ nums[i] ] ++;
        }
      }else {
        obj[ nums[i] ] = 1;
       
      }
    }
    return [...result];
};

但像 [1] 或 [1, 2] 這種 case 就會失效，但又怕重覆 [2, 2] 所以我必須新增一個 set 去存 result

var majorityElement = function(nums) {
    let obj = {};
    let len = nums.length;
    let judge = len/3;
    let result = new Set();

    for(let i = 0; i<len; i++){
      if(obj[ nums[i] ]) {

        if(obj[ nums[i] ] + 1 > judge){
          // add Here
          result.add( nums[i] )
        }else {
          obj[ nums[i] ] ++;
        }
      }else {
        obj[ nums[i] ] = 1;
        
        // add Here
        if(obj[ nums[i] ] > judge){
          result.add( nums[i] )
        }
      }
    }
    return [...result];
};

更佳解?

前面寫法其實有點亂因為一堆 if else for，換成以下寫法清楚超多

if(obj[ nums[i] ]) {
  obj[ nums[i] ] ++;
}else {
  obj[ nums[i] ] = 1;
}

// --可以用以下取代----------

(nums[i] in obj) ? obj[ nums[i] ] ++ : obj[ nums[i] ] = 1;

var majorityElement = function(nums) {
    let obj = {};
    let len = nums.length;
    let judge = len/3;
    let result = [];

    for(let i = 0; i<len; i++){
      (nums[i] in obj) ? obj[ nums[i] ] ++ : obj[ nums[i] ] = 1;
    }

    Object.keys(obj).forEach( key => {
      if(obj[key] > judge) result.push(key)
    })
   
    return result;
};