乐趣区

算法

1. 多数投票算法(Boyer-Moore Algorithm)

问题描述:
给定一个无序数组,有 n 个元素,找出其中的一个多数元素,多数元素出现的次数大于⌊ n/2 ⌋,注意数组中也可能不存在多数元素。
https://blog.csdn.net/kimixuc…


假设数组 a[n]

两个变量:
candidate: 多数元素的候选人
count: 候选人的生命.

初始化:
先以数组第一个数为 candidate,
count 设置为 1

过程:
遍历 1:
从第二个数开始遍历, 如果 a[i]==candidate -> count++;
如果 a[i] != candidate -> count–;
如果 count==0, 令 candidate=a[i],count=1;
遍历 2:
拿着当前的候选人去 candidate, 判断是否数量大于 n /2


如果有多数元素数量大于 n /2, 那么为什么一定是 candidate 呢?

可以这么假设,candidate 还是 candidate,令非 candidate 的数全部为 0。0 的数量少于 n / 2 肯定会在该过程中被耗尽,更别说把 0 分散成各种数的情况了。


分布式 Boyer-Moore
这个算法的另外一个优点就是可以分治归并。
把一个大数组分成多个小数组,然后分别算出 (candidate,count)
然后按相同的 candidate,将其 count 叠加,最后看哪个 count 比较高,为最终候选人。
再遍历一遍验证。

int MoreThanHalfNum_Solution(vector<int> numbers) {
    int candidate,count;
    int sum;
    candidate = numbers[0];
    count = 1;
    for(int i=1; i < numbers.size();i++){count = numbers[i] == candidate?++count:--count;
        if(count == 0){candidate = numbers[i];
            count = 1;
        }
    }
//    cout << candidate;
    sum = 0;
    for(int i = 0;i < numbers.size();i++){if(candidate == numbers[i]) sum++;
    }
    return sum>numbers.size()/2?candidate:0;}
退出移动版