---
# System prepended metadata

title: \#169 Majority Element
tags: [leetcode, leetcode-easy]

---

# \#169 Majority Element
## *取得數字陣列中的主要元素值(該值佔陣列長度一半以上)*
## Log
 - build 20210411 by syhuang

## 多數投票演算法(Boyer–Moore majority vote algorithm)
 - 核心概念:不同的票數兩兩相消, 最終結果並不影響其眾數
```javascript=
var majorityElement = function(nums) {
    //實作多數投票演算法
    var count = 0;
    var elm;
    for(var num of nums){
        if(count==0){
            elm = num;
            count++;
        }else if(elm!=num){ //不同元素相互抵銷
            count--;
        }else{  //elm==num
            count++;
        }
    }
    return elm;
};
```

## 排序解
 - 排序後取中間的元素(index=array.length/2)
```javascript=
var majorityElement = function(nums) {
    nums.sort();
    return nums[parseInt(nums.length/2)];
};
```
## 初見
 - 用map存元素出現的次數+迴圈判斷即可, edge case是陣列長度為1的情況直接回傳nums[0]
```javascript=
var majorityElement = function(nums) {
    if(nums.length==1) return nums[0];
    var map = new Map();
    for(var i=0; i<nums.length; i++){
        if(map.has(nums[i])){
            if(map.get(nums[i])>=Math.floor(nums.length/2)) return nums[i];
            map.set(nums[i],map.get(nums[i])+1);
        }else map.set(nums[i],1);
    }
};
```
## 備註
 - 解法有很多種,只記錄三種,其它[到此查看](https://leetcode.com/problems/majority-element/solution/)
## 參考
###### tags: `leetcode`, `leetcode-easy`