摩尔投票算法
- 来源: LeetCode-169 求众数
- 算法描述:
- 依次用数组中2个元素抵消法,相等+1,不等减-1,为0时重新取新的下标元素。这样超过一半的元素肯定是抵消不完的,就直接返回之前赋值的元素即可。
1
2
3
4
5
6
7
8
9
10
11
12
13public int MajorityElement(int[] nums) {
int countFlag = 0;
int result = 0;
for (int i = 0; i < nums.Length; i++)
{
if (countFlag == 0)
{
result = nums[i];
}
countFlag += (result == nums[i]) ? 1 : -1;
}
return result;
}
- 依次用数组中2个元素抵消法,相等+1,不等减-1,为0时重新取新的下标元素。这样超过一半的元素肯定是抵消不完的,就直接返回之前赋值的元素即可。