LeetCode 169. 多数元素

LeetCode 169. 多数元素

难度：$easy$

---

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

• $n==nums.length$
• $1<=n<=5\ast 10^4$
• $-10^9<=nums[i]<=10^9$

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

---

算法1

(哈希)

使用 C++ 提供的 unordered_map 记录每个元素出现的次数。
遍历过程在，如果次数大于 n/2，则返回该数字即可。

复杂度分析

• 时间复杂度：unordered_map 单次插入和查询的时间复杂度为 $O(1)$，故总时间复杂度为 $O(n)$

• 空间复杂度 : 至少需要额外的 $O(n)$ 的空间。

C++ 代码

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int, int> hash;int n = nums.size();int res = 0;for (int i = 0; i < n; i ++) {hash[nums[i]] ++;if (hash[nums[i]] > n / 2) res = nums[i];}return res;}
};

---

算法2

(投票算法)

1. 定义 cnt 计数器，初始为 0；candidate 记录答案。
2. 从头开始遍历数组，若发现 cnt == 0，则 candidate := nums[i]；然后若 candidate == nums[i]，cnt++；否则 cnt--。
3. 遍历结束后，若数组中存在主要元素，则主要元素必定是 candidate。

复杂度分析

• 时间复杂度：仅遍历一次数组，故时间复杂度为 $O(n)$

• 空间复杂度 : 仅使用了两个变量，故需要 $O(1)$ 的额外空间。

C++ 代码

class Solution {
public:int majorityElement(vector<int>& nums) {int cnt = 0, candidate;for (int i = 0; i < nums.size(); i ++) {if (cnt == 0) candidate = nums[i];if (nums[i] == candidate) cnt ++;else cnt --;}return candidate;}
};