写在前沿：本文代码均使用C语言编写。
Description：
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入:[3,2,3]输出:3
示例 2:
输入:[2,2,1,1,1,2,2]输出:2
Analysis：
一、排序法
根据题目给定的条件，众数定义为数组中出现次数大于N/2的元素，对数组重新排列后，位于数组N/2位置处的值就是数组的众数。
完整C 代码：
int majorityElement(int* nums, int numsSize) {
/*冒泡法对数组进行排序*/
for (int j=1;j<numsSize;j++){
for(int i=0;i<numsSize-j;i++){
int temp;
if(nums[i]>=nums[i+1]){
temp=nums[i+1];
nums[i+1]=nums[i];
nums[i]=temp;
}
}
}
return nums[numsSize/2];
}
总结：这种算法(简直不好意思称为算法)大概除了理解上简单直白外，基本是没有任何优点了，代码也有一定缺陷，调用函数求个众数顺带把原数组排序了惊不惊喜？另外这个算法LeetCode执行用时4348ms，速度是挺感人的。
二、摩尔投票算法
知乎用户@喝七喜 在问题如何理解摩尔投票算法？中已经描述的很清楚了，另外再贴上另外一位知乎网友@JoyHao 提供的演示实例(侵删)。由于数组中的众数个数大于n/2，那么对数组中两个不相等的数相互抵消，最后剩下的一个或者几个无法再进行消除的数，就是数组中的众数。
代码分析：假设初始众数(maj)为数组的第一个元素num[0]，count=1,当数组后续元素等于maj时，count++，否则count--。若count=0，说明到当前及之前所有元素抵消完毕，将下一个元素重新赋值给maj，同时count=1，由下一个元素开始重新做抵消。最后剩下的maj即为众数值。根据题目要求众数出现次数大于n/2，因此结果必定存在，同时count必定大于0。
完整C代码：
int majorityElement(int* nums, int numsSize) {
int maj=nums[0],count=1;
for (int i=1;i<numsSize;i++){
if(count==0){
maj=nums[i];
count++;
}
else if(maj==nums[i]){
count++;
}
else{
count--;
}
}
return maj;
}
总结：摩尔投票法的理解上并不会比排序法难，但是执行速度上有巨大的提升，LeetCode执行时间8ms算是一个还不错的结果。同时这个算法还可以扩展到比如出现次数大于n/3的元素这类问题，更重要的是也不会像排序法的函数那样给调用函数的人一点surprise。
网友评论