前言
暴力可以解，但是优化非常需要技巧
正文
问题来源
本问题来自leetcode上的169题。这道题自己用暴力方式能够解，但是就不献丑了。参考网上的博文。Leetcode 169
问题描述
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
分析：
采用摩尔投票算法
假设数组是：[1,2,1,1,2,1]。算法步骤如下：
- 1。当前大多数是1，得分置1
- 2。与当前大多数不同，得分 - 1，得分为0，当前大多数 = 1
- 1。与当前大多数不同，得分为0，所以设置当前大多数 1 -> 1，得分置1
- 1。与当前大多数相同，得分 + 1，得分为2，当前大多数 = 1
- 2。与当前大多数不同，得分 - 1 ，得分为1，当前大多数 = 1
- 1。与当前大多数相同，得分 + 1，得分为2，当前大多数 = 1
这意味着1是这个数组中出现次数过半的数。
可以感受得到，算法会保存一个当前大多数，和得分，当遇到一个数不是当前大多数时，得分会减一，当减到0时，大多数会发生改变，并且重置得分为1。
C代码如下：
int majorityElement(int* nums, int numsSize) {
int cur=0;
int n;
int i;
for(i=0;i<numsSize;i++)
{
if(cur==0) {n=nums[i];cur++;}
else if(nums[i]==n){cur++;}
else {cur--;}
}
return n;
}
总结：
摩尔投票算法，nice。
结语
闲来无事的话，多练习练习，做做题。
