169. Majority Element.md

169. Majority Element

思路

题目要求就是求数组主元素，主元素就是在数组中出现次数超过元素个数一半的元素，题目保证主元素一定存在。

思路一: 排序

若对数组nums进行排序，则nums[n/2]就是主元素。
时间复杂度为O(nlogn)。

思路二: 摩尔投票算法

因为主元素总是存在。所以每出现两个不一样的数就可以忽视这两个数。最终剩下的就是主元素。
我们可以从前往后遍历，如果某数和当前major相同那么count++，否则count--，如果count为零了，那么当前major应该改成当前这个数。
时间复杂度O(n)。

摩尔投票法的核心就是成对抵消，即删除不同的数。 举一个形象的例子（例子来源）：玩一个诸国争霸的游戏，假设你方人口超过天下总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。最差情况就是所有其他国家的人都联合起来对付你国（对应你每次选择作为计数器的数都是众数），但其实还存在其他国家也会相互攻击（会选择其他数作为计数器的数）的情况，但只要你们不要内斗，最后能剩下的必定是自己人，即最后肯定你国赢。

思路三: 位运算

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

时间复杂度O(n)。

思路四: 求中位数

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

C++

思路一

// 提交结果为16ms
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

思路二

// 提交结果为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;     
    }
};

思路三

// 提交结果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;
    }
};

思路四

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