力扣 169多数元素
题目：
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1： 输入：[3,2,3] 输出：3 实例 2： 输入：[2,2,1,1,1,2,2] 输出：2 来源：力扣（LeetCode）
如果不限定时间复杂度和空间复杂度，很容易想到的就是用Map 存储 元素 和他的出现次数
如果要求空间复杂度为O（1）呢?
下面是空间复杂度为O（1）的代码实现
class Solution {
public int majorityElement(int[] nums) {
int count=0;
int candidate = 0;
for (int i = 0; i < nums.length; i++) {
if(count==0){
candidate=nums[i];
}
if(nums[i]==candidate){
count++;
}else {
count--;
}
}
return candidate;
}
}
上面就是基于投票算法实现的代码。
摩尔投票算法是基于这个事实：
每次从集合里面选两个不同的数字抵消掉，最后剩下的一个数字或着多个相同的数字，就是出现次数大于总数一半的那个。
步骤：
1.维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
2.遍历数组 nums，如果count==0，先把x的值赋给candidate，然后在判断；
3.如果 x 与 candidate 相等，count++；
4.如果 x 与 candidate 不等，count- -,相当于拿出一个数值为candidate的数跟x抵消掉。
最后得到的结果就是答案。
有误请指正0.0
