> For the complete documentation index, see [llms.txt](https://hannahpun.gitbook.io/leetcode-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hannahpun.gitbook.io/leetcode-note/array/229-majority-element-ii.md).

# # 229 Majority Element II

[LeetCode](https://leetcode.com/problems/majority-element-ii/)   [169 的延伸題](https://hannahpun.gitbook.io/leetcode-note/array/169-majority-element)

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&#x20;

```
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;
};
```