Leetcode 169 -- 分治 | 摩尔投票法

题目描述

Majority Element

思路

分治法参考官方题解

其实这里的分治算法和归并排序很相像。

摩尔投票算法(同归于尽消杀法)

如果我们把出现次数大于数据长度一半的数记为 $+1$，把其他数记为 $-1$，将它们全部加起来，显然和大于 $0$。

证明

“同归于尽消杀法” ：
由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。

1. 遍历数组
2. 第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。
3. 如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主不变，winner 依然是当前这个士兵所属阵营，现存兵力 count 加一；
4. 如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。 此时前方阵营兵力-1, 即使双方都死光，这块高地的旗帜 winner 不变，没有可以去换上自己的新旗帜。
5. 当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，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]$ 就不存在众数。