題目

標題和出處

標題：多數元素 II

出處：229. 多數元素 II

難度

3 級

題目描述

要求

給定大小為 $\text{n}$ 的數組 $\text{nums}$，找出其中所有出現超過 $?\frac{\text{n}}{\text{3}}?$ 次的元素。

示例

示例 1：

輸入：$\text{nums?=?[3,2,3]}$
輸出：$\text{[3]}$

示例 2：

輸入：$\text{nums?=?[1]}$
輸出：$\text{[1]}$

示例 3：

輸入：$\text{nums?=?[1,2]}$
輸出：$\text{[1,2]}$

數據范圍

• $\text{n}=\text{nums.length}$
• $\text{1}\le \text{n}\le \text{5}\times {\text{10}}^{\text{4}}$
• ${\text{-10}}^{\text{9}}\le \text{nums[i]}\le {\text{10}}^{\text{9}}$

進階

你可以使用線性時間復雜度和 $\text{O(1)}$ 空間復雜度解決此問題嗎？

前言

這道題是「多數元素」的進階，要求找出數組中所有出現次數大于 $?\frac{n}{3}?$ 的元素。這道題也可以使用哈希表計數、排序和摩爾投票三種解法得到答案。

長度是 $n$ 的數組中，最多有 $2$ 個出現次數大于 $?\frac{n}{3}?$ 的元素。可以使用反證法證明。

假設有 $3$ 個出現次數大于 $?\frac{n}{3}?$ 的元素，這 $3$ 個元素的出現次數都不小于 $?\frac{n}{3}?+1$，因此這 $3$ 個元素的總出現次數至少為 $3\times ?\frac{n}{3}?+3$。由于 $?\frac{n}{3}?>\frac{n}{3}?1$，因此 $3\times ?\frac{n}{3}?+3>3\times (\frac{n}{3}?1)+3=3\times \frac{n}{3}?3+3=n$，即這 $3$ 個元素的總出現次數一定超過 $n$，和數組長度是 $n$ 矛盾。因此數組中不可能有 $3$ 個出現次數大于 $?\frac{n}{3}?$ 的元素，最多有 $2$ 個出現次數大于 $?\frac{n}{3}?$ 的元素。

解法一

思路和算法

最直觀的解法是統計數組中每個元素的出現次數，然后尋找出現次數大于 $?\frac{n}{3}?$ 的元素。

遍歷數組，使用哈希表記錄每個元素的出現次數，遍歷結束之后即可得到數組中每個元素的出現次數。然后遍歷哈希表，對于哈希表中的每個元素得到出現次數，將出現次數大于 $?\frac{n}{3}?$ 的元素添加到結果中。

代碼

class Solution {public List<Integer> majorityElement(int[] nums) {Map<Integer, Integer> counts = new HashMap<Integer, Integer>();for (int num : nums) {counts.put(num, counts.getOrDefault(num, 0) + 1);}List<Integer> majorities = new ArrayList<Integer>();int n = nums.length;Set<Integer> set = counts.keySet();for (int num : set) {if (counts.get(num) > n / 3) {majorities.add(num);}}return majorities;}
}

復雜度分析

• 時間復雜度：$O(n)$，其中 $n$ 是數組 $\text{nums}$ 的長度。遍歷數組統計每個元素的出現次數需要 $O(n)$ 的時間，遍歷哈希表得到多數元素也需要 $O(n)$ 的時間。

• 空間復雜度：$O(n)$，其中 $n$ 是數組 $\text{nums}$ 的長度。需要創建哈希表記錄每個元素的出現次數，哈希表中的元素個數不超過 $n$。

解法二

思路和算法

首先將數組排序，排序后的數組滿足相等的元素一定出現在數組中的相鄰位置。如果一個元素在數組中的出現次數大于 $?\frac{n}{3}?$，則排序后的數組中存在至少 $?\frac{n}{3}?+1$ 個連續的元素都等于該元素，即一定存在兩個差為 $?\frac{n}{3}?$ 的下標處的元素都等于該元素。

將數組 $\text{nums}$ 排序之后遍歷數組 $\text{nums}$，對于下標 $i$，當 $i\ge ?\frac{n}{3}?$ 時，如果 $\text{nums}[i]=\text{nums}[i??\frac{n}{3}?]$，則 $\text{nums}[i]$ 是出現次數大于 $?\frac{n}{3}?$ 的元素。

為了避免重復計算，當 $i<n?1$ 且 $\text{nums}[i]=\text{nums}[i+1]$ 時跳過下標 $i$，只有當下標 $i$ 的右側沒有與 $\text{nums}[i]$ 相等的元素時才判斷 $\text{nums}[i]=\text{nums}[i??\frac{n}{3}?]$ 是否成立，如果成立則將 $\text{nums}[i]$ 添加到結果中。

代碼

class Solution {public List<Integer> majorityElement(int[] nums) {Arrays.sort(nums);List<Integer> majorities = new ArrayList<Integer>();int n = nums.length;for (int i = n / 3; i < n; i++) {int num = nums[i];if (i < n - 1 && num == nums[i + 1]) {continue;}if (num == nums[i - n / 3]) {majorities.add(num);}}return majorities;}
}

復雜度分析

• 時間復雜度：$O(n\log n)$，其中 $n$ 是數組 $\text{nums}$ 的長度。排序需要 $O(n\log n)$ 的時間。

• 空間復雜度：$O(\log n)$，其中 $n$ 是數組 $\text{nums}$ 的長度。排序需要 $O(\log n)$ 的遞歸調用棧空間。

解法三

思路和算法

原始的摩爾投票算法用于找到出現次數大于一半的元素，其時間復雜度是 $O(n)$，空間復雜度是 $O(1)$。摩爾投票算法可以推廣到尋找出現次數大于 $?\frac{n}{k}?$ 的元素，其中 $k$ 是大于 $1$ 的正整數。

由于出現次數大于 $?\frac{n}{3}?$ 的元素不可能超過 $2$ 個，因此維護 $2$ 個候選元素 ${\text{majority}}_1$ 和 ${\text{majority}}_2$，以及兩個候選元素的出現次數 ${\text{count}}_1$ 和 ${\text{count}}_2$，初始時候選元素和出現次數都是 $0$。

遍歷數組，當遍歷到元素 $\text{num}$ 時，執行如下操作。

1. 比較 $\text{num}$ 是否和候選元素相等，如果相等則將相應的出現次數加 $1$。

   1. 如果 $\text{num}={\text{majority}}_1$，則將 ${\text{count}}_1$ 加 $1$。

   2. 否則，如果 $\text{num}={\text{majority}}_2$，則將 ${\text{count}}_2$ 加 $1$。

2. 如果 $\text{num}$ 和兩個候選元素都不相等，則判斷兩個候選元素的出現次數是否為 $0$，如果為 $0$ 則更新候選元素和出現次數。

   1. 如果 ${\text{count}}_1=0$，則將 ${\text{majority}}_1$ 更新為 $\text{num}$，并將 ${\text{count}}_1$ 加 $1$。

   2. 否則，如果 ${\text{count}}_2=0$，則將 ${\text{majority}}_2$ 更新為 $\text{num}$，并將 ${\text{count}}_2$ 加 $1$。

3. 如果 $\text{num}$ 和兩個候選元素都不相等且兩個候選元素的出現次數都大于 $0$，則 $\text{num}$ 和兩個候選元素抵消，將 ${\text{count}}_1$ 和 ${\text{count}}_2$ 都減 $1$。

遍歷結束之后，得到兩個候選元素。再次遍歷數組，統計兩個候選元素在數組中的出現次數，當出現次數大于 $?\frac{n}{3}?$ 時將候選元素添加到結果中。

代碼

class Solution {public List<Integer> majorityElement(int[] nums) {int majority1 = 0, majority2 = 0;int count1 = 0, count2 = 0;for (int num : nums) {if (num == majority1) {count1++;} else if (num == majority2) {count2++;} else if (count1 == 0) {majority1 = num;count1++;} else if (count2 == 0) {majority2 = num;count2++;} else {count1--;count2--;}}count1 = 0;count2 = 0;for (int num : nums) {if (num == majority1) {count1++;} else if (num == majority2) {count2++;}}List<Integer> majorities = new ArrayList<Integer>();int n = nums.length;if (count1 > n / 3) {majorities.add(majority1);}if (count2 > n / 3) {majorities.add(majority2);}return majorities;}
}

復雜度分析

• 時間復雜度：$O(n)$，其中 $n$ 是數組 $\text{nums}$ 的長度。需要遍歷數組 $\text{nums}$ 兩次。

• 空間復雜度：$O(1)$。