Leetcode 169.多数元素

题目描述：

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

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

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

示例 1：

1
2

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

示例 2：

1
2

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

链接：

https://leetcode-cn.com/problems/majority-element

题目分析

1.哈希表

  先不考虑进阶要求的话最容易想到的方法就是建立一个哈希表，只需要遍历一次数组并且记录每个数字出现的次数即可。在遍历的同时我们维护出现次数最多的元素，就无需再对哈希表进行一次遍历寻找最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> count;
        int major, max = 0;
        for(int num : nums){
            count[num]++;
            if(count[num] > max){
                major = num;
                max = count[num];
            }
        }
        return major;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组元素的个数。我们对数组进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 是数组元素的个数。由于数组中存在多数元素，因此其实数组中最多只有 $n-\lfloor n/2\rfloor$ 种不同的元素。而我们主要的空间开销就是哈希表，哈希表的最大大小就是 $n-\lfloor n/2\rfloor$，也即是 $O(n)$。

2.排序

  由于数组中存在多数元素，如果对整个数组进行排序，则多数元素肯定占据了数组一半以上的空间，则数组的中位数肯定就是多数元素。

1
2
3
4
5
6
7

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};

  时间复杂度：$O(n\log n)$，其中 $n$ 是数组元素的个数。也即排序所需的时间复杂度。
  空间复杂度：$O(\log n)$ 或 $O(1)$。取决于排序函数所需的空间，使用自带的排序函数应该是 $O(\log n)$ 的。

3.摩尔投票

  如何实现进阶要求中的 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度呢？由于多数元素占了数组一半以上的数量，则把每个众数记为+1，非众数记为-1，最后得到的结果依然是正数。则我们维护一个众数和一个投票数，如果遍历到的数字是众数则投票数+1，不是则投票数-1，当投票数为 0 时当前众数需要更换，保证投票数非负。这样存在着一个问题：局部众数并不一定是全局的众数，在未获得真正的众数之前，情况会是怎么样的？
  假如当前维护的众数并不是真正的众数，则遇到真正的众数时投票数会-1，遇到虚假的众数时会+1，刚好也是符合我们所想要的“抵消”关系，而遇到其他不是当前众数也不是真正众数的数字投票数也会-1，这样只会更快地导致当前虚假众数“下台”。而真正众数的数量是比其他所有数都多的，因此最后推举出来的众数一定会是真正的众数。当前维护的众数如果是真正的众数则投票一切正常。综上所述，我们可以得到正确结果。
  这样我们只需要维护一个当前众数和一个投票数，对数组进行一次遍历进行投票即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major = 0;
        int vote = 0;
        for(int num : nums){
            if(vote == 0){
                major = num;
                vote++;
            }
            else if(num == major) vote++;
            else vote--;
        }
        return major;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组元素的个数。我们只对数组进行了一次遍历。
  空间复杂度：$O(1)$。我们只需要常数的空间存放变量。