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]\) 就不存在众数。