题目描述

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

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

样例

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

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

算法1

(unordered_map) $O(n)$

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

时间复杂度

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

空间复杂度

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

C++ 代码

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

算法3

(投票算法) $O(n)$

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 (candidate == nums[i])
                cnt++;
            else
                cnt--;
        }
        return candidate;
    }
};