【面试经典150 | 数组】多数元素

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

---

Tag

【多数投票法】【哈希表】【数组】

---

题目来源

面试经典 150 题 —— 169. 多数元素

---

题目解读

给定一个数组 nums，返回数组中的多数元素，多数元素指的是出现次数大于 $\lfloor n/2\rfloor$ 的元素。数组 nums 非空并且一定存在多数元素。

---

解题思路

方法一：哈希表

多数元素出现的次数大于 $\lfloor n/2\rfloor$，该多数元素一定是数组中出现次数最多的元素，因此可以想到利用哈希表记录每个元素出现的次数，返回出现次数最多的元素即可。

在具体实现中，可以一边更新哈希表，一边更新当前出现次数最大的数，这样可以省去一次遍历操作。

实现代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int res = 0, cnt = 0;
        unordered_map<int, int> cnts;
        for (int num : nums) {
            ++cnts[num];
            if (cnts[num] > cnt) {
                res = num;
                cnt = cnts[num];
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 nums 的长度。

空间复杂度：$O(n)$，使用一个哈希表存放数组 nums 中元素出现的个数。

方法二：排序

首先对数组 nums 进行排序，升序或者降序都可以，下标为 $\lfloor n/2\rfloor$ 元素一定就是多数元素。

实现代码

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

复杂度分析

时间复杂度：$O(nlogn)$，$n$ 为数组 nums 的长度。

空间复杂度：$O(nlogn)$，求多数元素没有使用额外的空间，这个额外的空间是排序算法占用的时间。

方法三：摩尔投票法

现在来介绍一种时间复杂度为 $O(n)$，空间复杂度为 $O(1)$ 的解法。

博耶-摩尔多数投票算法，也称作 多数投票算法，摩尔投票算法。这一算法由罗伯特·S·博耶和J·斯特罗瑟·摩尔在1981年发表，也是处理数据流的一种典型算法。

多数投票算法解决的问题是：如何在众多候选人中，选出得票最多的那一个，和本题需要解决的问题一致。

在投票问题中，如果当前的唱票结果和上一次的结果一致，则得票的候选人票数 +1；否则，将上一个得票的候选人票数 -1，并判断，如果此时的票数 < 0，则当前得票的候选人会取代上一个候选人成为新的候选人，其得票数置为 1。

于是在本题中，维护一个 majority 表示众数，一个 cnt 表示当前众数的数量，遍历数组 nums，设当前数字为 num：

• 如果 num = majority，则 ++cnt；
• 否则，先 --cnt，如果 cnt < 0，则 majority = num 并且 cnt = 1；
• 上一步中的先 -- 再判断，可以用一步实现 --cnt < 0。

最后返回 majority 就是题目中要求的多数元素。

实现代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int res = -1;
        int cnt = 0;
        for (int num : nums) {
            if (num == res) {
                ++cnt;
            }
            else if (--cnt < 0) {
                res = num;
                cnt = 1;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 nums 的长度，因为只需要一次遍历就能解决该问题。

空间复杂度：$O(1)$，仅使用了有限个变量。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。