Boyer-Moore Majority Voting Algorithm——摩尔投票法
gfg上的链接
AcWing52.数组中出现次数超过一半的数字
(我自己试的时候用的排序,也可以过,但主要学习一下这个算法)
在时间复杂度O(n)、空间复杂度O(1)下完成对于数组出现次数超过一半的数字的查找
如下,是在一定有解的前提下的查找,选candidate,一样就票+1,不一样就票-1,最后剩下的票数大于0的candidate一定是答案
如果题中可能无解,即可能没有出现次数超过一半的数字,需要在后面加一个循环,下面给出了代码
class Solution {
public int moreThanHalfNum_Solution(int[] nums) {
int n = nums.length;
int cnt = 0, candidate = -1;
for(int i=0; i<n ;i++) {
if(cnt == 0) {
candidate = nums[i];
cnt = 1;
} else {
if(nums[i] == candidate) {
cnt++;
} else {
cnt--;
}
}
}
return candidate;
}
}
补充的循环
// Checking if majority candidate occurs more than n/2 times
count = 0;
for (int index = 0; index < nums.length; index++) {
if (nums[index] == candidate)
count++;
}
if (count > (nums.length / 2))
return candidate;
return -1;
排序方法
class Solution
{
static int majorityElement(int a[], int size)
{
if((size == 2 && a[0] != a[1])) {
return -1;
}
Arrays.sort(a);
int mid = a[size/2];
int cnt = 0;
for(int i=0; i<size; i++) {
if(a[i] == mid) {
++cnt;
}
}
if(cnt > size/2) return mid;
return -1;
}
}