题目描述
思路
其实这里的分治算法和归并排序很相像。
摩尔投票算法(同归于尽消杀法)
如果我们把出现次数大于数据长度一半的数记为 \(+1\),把其他数记为 \(−1\),将它们全部加起来,显然和大于 \(0\)。
证明
“同归于尽消杀法” :
由于多数超过50%, 比如100个数,那么多数至少51个,剩下少数是49个。
- 遍历数组
- 第一个到来的士兵,直接插上自己阵营的旗帜占领这块高地,此时领主 winner 就是这个阵营的人,现存兵力 count = 1。
- 如果新来的士兵和前一个士兵是同一阵营,则集合起来占领高地,领主不变,winner 依然是当前这个士兵所属阵营,现存兵力 count 加一;
- 如果新来到的士兵不是同一阵营,则前方阵营派一个士兵和它同归于尽。 此时前方阵营兵力-1, 即使双方都死光,这块高地的旗帜 winner 不变,没有可以去换上自己的新旗帜。
- 当下一个士兵到来,发现前方阵营已经没有兵力,新士兵就成了领主,winner 变成这个士兵所属阵营的旗帜,现存兵力 count ++。
就这样各路军阀一直厮杀以一敌一同归于尽的方式下去,直到少数阵营都死光,剩下几个必然属于多数阵营的,winner 是多数阵营。
(多数阵营 51个,少数阵营只有49个,死剩下的2个就是多数阵营的人)
投票算法证明:
如果候选人不是 maj ,则 maj 会和其他非候选人一起反对,所以候选人一定会下台(maj==0时发生换届选举)
如果候选人是 maj , 则 maj 会支持自己,其他候选人会反对,同样因为 maj 票数超过一半,所以maj 一定会成功当选
代码-分治
class Solution {
public:
int get_range(vector<int> &nums, int l, int r, int target)
{
int cnt = 0;
for(int i = l; i <= r; i ++ )
if(nums[i] == target) cnt ++ ;
return cnt;
}
int merge(vector<int> &nums, int l, int r)
{
if(l == r) return nums[l];
int mid = l + r >> 1;
int left_candidate = merge(nums, l, mid);
int right_candidate = merge(nums, mid + 1, r);
if(left_candidate != right_candidate)
{
if(get_range(nums, mid + 1, r, right_candidate) >= get_range(nums, l, mid, left_candidate))
return right_candidate;
}
return left_candidate;
}
int majorityElement(vector<int>& nums) {
return merge(nums, 0, nums.size() - 1);
}
};
代码–摩尔投票
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = -1, count = 0;
for(auto &x : nums) {
if(count == 0) {
candidate = x;
count = 1;
}
else {
count += (x == candidate ? 1 : -1);
}
}
return candidate;
}
};
众数
众数指的是一组数据当中出现次数最多的数,若数据的数据值出现次数相同且无其他数据值时,则不存在众数。
例如 \([1, 2, 2, 1]\) 就不存在众数。
原文地址:http://www.cnblogs.com/ALaterStart/p/16813085.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性