多数元素
方法一：暴力解法
直接利用两层循环，外层循环用来枚举数组的每一个元素，内层循环用来计算每个元素出现的次数，这样就可以求出多数元素了。
显然，这个方法的时间复杂度为O(N^2)，效率太低。
int majorityElement(int* nums, int numsSize) { int max_index = 0; //用来记录多数元素的下标 int temp = 0; //用来统计每个元素出现的次数 int max = 0; //用来记录出现的最大次数 for (int i = 0; i < numsSize; i++) { temp = 0; //每一次都是对一个新的元素记录，因此temp要置零 //如果出现重复元素，那么就temp++ for (int j = 0; j < numsSize; j++) { if (nums[i] == nums[j]) temp++; } //如果temp大于最大次数，那么就更新多数元素下标，同时更新max if (temp > max) { max_index = i; max = temp; } } //返回多数元素 return nums[max_index]; }
方法二：排序
先给出结论：如果一个有序数组中存在多数元素（出现次数大于n/2），那么下标为n / 2处的元素就是多数元素
下面通过画图来分析：
我们利用快速排序qsort来实现，时间复杂度为O(NlongN)，效率有所提高，但仍无法满足题目要求
int compar(const void* num1, const void* num2) { return *(int*)num1 - *(int*)num2; } int majorityElement(int* nums, int numsSize){ //排序 qsort(nums,numsSize,sizeof(int),compar); //返回多数元素 return nums[numsSize/2]; }
（推荐）方法三：互拼法（Boyer-Moore 投票算法）
我们来举一个形象的例子来解释这个算法：
假设有100个士兵，由于多数元素必然大于n/2，那我们假设多数元素士兵为51个，其他元素士兵为49个，这100个士兵一起去占领一块高地（相同士兵共存，不同士兵相消）
- 第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，现存兵力 count = 1。
- 如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，~~~~现存兵力 count++；
- 如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。 此时前方阵营兵力count --。
- 当下一个士兵到来，发现前方阵营已经没有兵力（双方死光），新士兵就成了领主，现存兵力 count ++。
就这样各路军阀一直以这种以一敌一同归于尽的方式厮杀下去，直到少数阵营都死光，那么最后剩下的几个必然属于多数阵营。（多数阵营 51个，少数阵营只有49个，死剩下的2个就是多数阵营的人）
这一题也一样，数组的第一个元素就是第一个士兵，，同时我们假设第一个元素就是要返回的多数元素temp，接下来遍历整个数组，如果遇到相同元素，那么count++，否则count--，如果count减为0，那么下一个元素就会成为多数元素，temp也要改变，最后遍历完数组得到的temp就是未被抵消的元素，即多数元素
这样，只需要遍历一遍数组，就可以得到想要的结果，时间复杂度为O(N)
int majorityElement(int* nums, int numsSize){ int temp = nums[0]; int count = 0; for(int i = 0; i < numsSize; i++) { if(temp == nums[i]) count++; else count--; if(count == 0) temp = nums[i + 1]; } return temp; }
