LeetCode/solutions/169. Majority Element.md

# [169. Majority Element](https://leetcode.com/problems/majority-element/description/)
# 思路
题目要求就是求数组主元素，主元素就是在数组中出现次数超过元素个数一半的元素，题目保证主元素一定存在。
## 思路一: 排序
若对数组nums进行排序，则nums[n/2]就是主元素。    
时间复杂度为O(nlogn)。 

## 思路二: 摩尔投票算法  
因为主元素总是存在。所以每出现两个不一样的数就可以忽视这两个数。最终剩下的就是主元素。  
我们可以从前往后遍历，如果某数和当前major相同那么count++，否则count--，如果count为零了，那么当前major应该改成当前这个数。    
时间复杂度O(n)。
> 摩尔投票法的核心就是成对抵消，即删除不同的数。
举一个形象的例子[（例子来源）](https://www.zhihu.com/question/49973163/answer/617122734)：玩一个诸国争霸的游戏，假设你方人口超过天下总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。最差情况就是所有其他国家的人都联合起来对付你国（对应你每次选择作为计数器的数都是众数），但其实还存在其他国家也会相互攻击（会选择其他数作为计数器的数）的情况，但只要你们不要内斗，最后能剩下的必定是自己人，即最后肯定你国赢。

## 思路三: 位运算
如果将每个数都转换为二进制的话，那么对于每一位上就只能是0或1。对每一位，取出现次数较多的数(0或1)，这样组成的数就是主元素。   

时间复杂度O(n)。

## 思路四: 求中位数

思路一对nums进行了排序，然后nums[n/2]就是主元素。其实不用完全排序，我们可以用快排partition的思想在O(n)的平均时间复杂度内求得中位数（见[215求第k大的数题解](215.%20Kth%20Largest%20Element%20in%20an%20Array.md)）。我们可以使用STL中的`nth_element`，`nth_element`保证第k(从0开始)个元素是位于最终排序位置的，所以我们令 k = size/2 即把中位数放在了最终位置。




# C++
## 思路一
``` C++
// 提交结果为16ms
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};
```
## 思路二
``` C++
// 提交结果为12ms，较思路一有提升
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major = nums[0], count = 0;
        for(int num : nums){ // 范围for语句
            if(major == num) count++;
            else if(count == 1) major = num;
            else count--;   
        }
        return major;     
    }
};
```
## 思路三
``` C++
// 提交结果20ms
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        vector<int>bit(32);
        for (int num: nums){
            for (int i = 0; i < 32; i++) 
                if(num & (1 << i)) bit[i]++;   
        }

        int major=0;
        for (int i = 0; i < 32; i++)
            if(bit[i] > nums.size() / 2) major |= (1 << i);
        return major;
    }
};
```

## 思路四
``` C++
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        return nums[nums.size() / 2];
    }
};
```