Leetcode 169-多数元素

Leetcode 169-多数元素

给定一个大小为n的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例1：

输入：nums = [3,2,3]
输出：3

示例2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= \(5*10^4\)
• \(-10^9\) <= nums[i] <= \(10^9\)

解析

看到这道题第一时间想到的是利用哈希表来完成，遍历整个数组，将元素作为哈希表的key值，将元素出现的次数作为哈希表的value值，最后遍历整个哈希表，找出出现次数大于 ⌊ n/2 ⌋ 的元素。

代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> hash;
        for(int i=0;i<nums.size();i++){
            hash[nums[i]]++;
        }
        for(auto p:hash){
            if(p.second > nums.size()/2){
                return p.first;
            }
        }
        return 0;
    }
};

正常通过。

在翻评论区和题解时发现了一种之前从未了解过的算法：Boyer-Moore 投票算法，于是对这种算法进行了了解，重做了这道题目。

Boyer-Moore 投票算法

摩尔投票是一种用来解决绝对众数问题的算法。

在一个集合中，如果一个元素的出现次数比其他所有元素的出现次数之和还多，那么就称它为这个集合的绝对众数。等价地说，绝对众数的出现次数大于总元素数的一半。

摩尔投票的过程非常简单，让我们把找到绝对众数的过程想象成一次选举。我们维护一个$ m$ ，表示当前的候选人，然后维护一个 \(cnt\) 。对于每一张新的选票，如果它投给了当前的候选人，就把 \(cnt\) 加1，否则就把 \(cnt\) 减1（也许你可以想象成，\(B\)的一个狂热支持者去把\(A\)的一个支持者揍了一顿，然后两个人都没法投票）。特别地，计票时如果 \(cnt=0\) ，我们可以认为目前谁都没有优势，所以新的选票投给谁，谁就成为新的候选人。

如果我们要求的是众数，这样的做法并不能给出正确答案，但如果要求的是绝对众数（且绝对众数确实存在），那么 m 一定是正确的。

这是因为，在最后计票时，我们知道有 \(cnt\) 张票投给了$ m$ ，假如绝对众数另有其人，那么一定是剩下的票投出来的。但剩下的 \(n−cnt\) 张票都是在“捉对厮杀”的过程中被抵消掉的，每一对被抵消的票都来自不同的候选人，所以一个候选人最多在这里拿到 \(\frac{n-cnt}{2}\) 票，这不可能大于 \(\frac{n}{2}\)。但绝对众数确实存在，所以这个绝对众数就一定是 \(m\) 。

如果绝对众数不存在，摩尔投票会给出一个错误的解，所以一定要记得验证答案。

这个算法是 \(O(n)\) 时间复杂度、 \(O(1)\) 空间复杂度的。

由于这道题目的特殊性，我们无需验证答案的正确性，只需要找出答案即可。

代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int winner=nums[0];
        int cnt = 0 ;
        for(auto tmp : nums){
            if(tmp == winner){
                cnt++;
            }else if(cnt == 0 ){
                winner=tmp;
                cnt=1;
            }else{
                cnt--;
            }
        }
        return winner;
        }
};

成功AC。