?
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; } };
2、对于一个排序数组来说，若众数存在，众数肯定是中间那个数。
class Solution {
public:
int majorityElement(vector
&num) {
std::sort(num.begin(), num.end());
return num[num.size()/2];
}
};
3、投票算法。可以想成打擂台，台上那个人若输赢次数相同，则下台，最后打败他的人上台。众数肯定是最后的赢家。这个算法用的时间最少了。
?
?
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; i
4、位算法。考虑到每个数都可以用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; } };
?
?