[LeetCode] Majority Element

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 &num) {
        int len = num.size();
        map count;
        for(int i=0; i len/2){
                return num[i];
            }
        }
        return 0;
    }
};

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

class Solution {
public:
    int majorityElement(vector &num) {
        int len = num.size();
        if(len==0){
            return 0;
        }
        int candidate = num[0];
        int count = 1;
        for(int i=1; i4、位算法。考慮到每個數都可以用32位二進制表示，對每個數的每一位二進制為1的計數，若某個二進制位的計數大於n/2，肯定有眾數的貢獻。這種辦法很新穎，雖然速度比不上投票算法，但是開拓思維嘛。這裡說一點，第一種方法中，定義了map count，對於每個新加入的鍵值，其值默認為0，但是對於int數組類型，每個數組初始化為隨機值，因此要用memset函數呀。
 
 
class Solution {
public:
    int majorityElement(vector &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/2)         //第i位為1的計數大於一半，肯定有眾數的貢獻
                result += (int)pow(2, i);
        }
        return result;
    }
};