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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

1.一开始不说了，太惨了，用开hash表又一次超时了，以下为超时代码

typedef struct mnode
{
int num;
int times;
struct mnode *next;
}node;
int majorityElement(int* nums, int numsSize) {
node *myhead[numsSize];
for(int i = 0; i < numsSize; i++) { myhead[i] = NULL; } //node *mylist =(node *)malloc(sizeof(node)*numSize); //memset(mylist,0,sizeof(node)*numsSize); for(int i = 0; i < numsSize;i++) { int k = nums[i]%numsSize; if(myhead[k] == NULL) { myhead[k]=(node *)malloc(sizeof(node)); memset(myhead[k],0,sizeof(node)); myhead[k]->next = NULL;
myhead[k]->num = nums[i];
myhead[k]->times = 1;
}
else
{
node * temp = myhead[k];
while(temp->next!=NULL)
{
if(temp->num == nums[i])
{
temp->times++;
continue;
}
temp = temp->next;
}
temp->next = (node *)malloc(sizeof(node));
memset(temp->next,0,sizeof(node));
temp->next->next = NULL;
temp->next->num = nums[i];
temp->next->times = 1;
}
}
node * max =NULL;
for(int i = 0; i < numsSize;i++) { node *temp = myhead[i]; while(temp !=NULL) { if(max != NULL) { if(temp ->times > max->times)
max = temp;
}
else
{
max = temp;
}
temp = temp->next;
}
}

}


之后查了查，发现有一种写法，就是既然必然有解，这个解的数量还大于n／2，呢么我每次删去两个数字统计，最终剩下的就是要求的，这个同理可以推广到n／k，每次统计k－1组删去不同的k个 最终留下的就是。反正我发现，在oj里，凡是求一个数的，你要算全部必然超时。。。

class Solution {
public:
int majorityElement(vector& nums) {
int candidate = 0;
int count = 0;
for(int i = 0; i < nums.size(); i ++) { if(count == 0) { candidate = nums[i]; count = 1; } else { if(nums[i] == candidate) count ++; else count --;／／由于本次没有加，直接减了实际上就是剪掉了2个数的统计 } } return candidate; } };
转自：中国cnblog