Majority Element

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

S1: hashmap O(n)time O(n) space

S2: sort然后返回中间值 nums[nums.size()/2] O(nlogn)time O(1)space

S3: Moore’s Voting Algorithm O(n)time O(1)space if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. more explain

我们这里只是找到majority element，并没有验证，因为题中确认一定存在majority element。若没有一定存在的条件，是需要验证的。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majElement = nums[0];
        int count = 1;
        for(int i = 1; i < nums.size(); ++i){
            if(count == 0) majElement = nums[i];
            if(nums[i] == majElement) count++;
            else count--;
        }
        return majElement;
    }
};

229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

S: Moore’s Voting Algorithm O(n)time O(1)space

Moore's voting algorithm的推广：找到出现次数大于floor[n/k]的所有元素。这种元素最多有k-1个，假设存在k-1个这种元素（不存在也没关系），把所有元素分为k组，其中有k-1组元素出现次数大于n/k（majority组），那么剩下的一组元素出现次数一定小于n/k（minority组），所以majority组元素出现次数减去minority组元素出现次数的值一定大于0.

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int maj1 = 0, maj2 = 0; 
        int count1 = 0, count2 = 0;
        for(auto num: nums){
            //考虑清楚每个if条件之间是否互斥
            if(num == maj1) count1++;
            else if(num == maj2) count2++;
            else if(count1 == 0) {maj1 = num; count1 = 1;}
            else if(count2 == 0) {maj2 = num; count2 = 1;}
            else{
                count1--;
                count2--;
            }
        }
        vector<int> result;
        count1 = 0; count2 =0;
        for(auto num: nums){
            if(num == maj1) count1++;
            if(num == maj2) count2++;
        }
        if(count1 > nums.size()/3) result.push_back(maj1);
        if(count2 > nums.size()/3 && maj2 != maj1) result.push_back(maj2);
        return result;
    }
};