康瑞部落

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.

解题思路：

1、用一个map记录每个数的出现的次数。若出现某个数的计数大于n/2，返回该数。

class Solution {
public:
    int majorityElement(vector<int> &num) {
        int len = num.size();
        map<int, int> count;
        for(int i=0; i<len; i++){
            count[num[i]]++;
            if(count[num[i]] > len/2){
                return num[i];
            }
        }
        return 0;
    }
};

2、对于一个排序数组来说，若众数存在，众数肯定是中间那个数。

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

3、投票算法。可以想成打擂台，台上那个人若输赢次数相同，则下台，最后打败他的人上台。众数肯定是最后的赢家。这个算法用的时间最少了。

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

4、位算法。考虑到每个数都可以用32位二进制表示，对每个数的每一位二进制为1的计数，若某个二进制位的计数大于n/2，肯定有众数的贡献。这种办法很新颖，虽然速度比不上投票算法，但是开拓思维嘛。这里说一点，第一种方法中，定义了map<int, int> count，对于每个新加入的键值，其值默认为0，但是对于int数组类型，每个数组初始化为随机值，因此要用memset函数呀。

class Solution {
public:
    int majorityElement(vector<int> &num) {
        int len = num.size();
        if(len==0){
            return 0;
        }
        int bitCount[32];
        memset(bitCount, 0, 32*sizeof(int));
        for(int i=0; i<len; i++){
            for(int j=0; j<32; j++){
                if(num[i]&(1<<j)){  //第j位是1
                    bitCount[j]++;
                }
            }
        }
        int result=0;
        for(int i=0; i<32; i++){
            if(bitCount[i] > len/2)         //第i位为1的计数大于一半，肯定有众数的贡献
                result += (int)pow(2, i);
        }
        return result;
    }
};

二次刷题（2015-08-06）

投票算法：

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