算法

jiezi

5 年前

问题描述:
给定一个无序数组，有 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;}

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