[LeetCode] Majority Element

Majority Element

Given an array of sizen, 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位是1bitCount[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;}};

有事者，事竟成;破釜沉舟，百二秦关终归楚;苦心人，