排序题目：多数元素 II

题目

标题和出处

标题：多数元素 II

出处：229. 多数元素 II

难度

3 级

题目描述

要求

给定大小为 $\text{n}$ 的数组 $\text{nums}$，找出其中所有出现超过 $\lfloor \frac{\text{n}}{\text{3}}\rfloor$ 次的元素。

示例

示例 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)}$ 空间复杂度解决此问题吗？

前言

这道题是「多数元素」的进阶，要求找出数组中所有出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 的元素。这道题也可以使用哈希表计数、排序和摩尔投票三种解法得到答案。

长度是 $n$ 的数组中，最多有 $2$ 个出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 的元素。可以使用反证法证明。

假设有 $3$ 个出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 的元素，这 $3$ 个元素的出现次数都不小于 $\lfloor \frac{n}{3}\rfloor +1$，因此这 $3$ 个元素的总出现次数至少为 $3\times \lfloor \frac{n}{3}\rfloor +3$。由于 $\lfloor \frac{n}{3}\rfloor >\frac{n}{3}-1$，因此 $3\times \lfloor \frac{n}{3}\rfloor +3>3\times (\frac{n}{3}-1)+3=3\times \frac{n}{3}-3+3=n$，即这 $3$ 个元素的总出现次数一定超过 $n$，和数组长度是 $n$ 矛盾。因此数组中不可能有 $3$ 个出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 的元素，最多有 $2$ 个出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 的元素。

解法一

思路和算法

最直观的解法是统计数组中每个元素的出现次数，然后寻找出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 的元素。

遍历数组，使用哈希表记录每个元素的出现次数，遍历结束之后即可得到数组中每个元素的出现次数。然后遍历哈希表，对于哈希表中的每个元素得到出现次数，将出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 的元素添加到结果中。

代码

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$。

解法二

思路和算法

首先将数组排序，排序后的数组满足相等的元素一定出现在数组中的相邻位置。如果一个元素在数组中的出现次数大于 $\lfloor \frac{n}{3}\rfloor$，则排序后的数组中存在至少 $\lfloor \frac{n}{3}\rfloor +1$ 个连续的元素都等于该元素，即一定存在两个差为 $\lfloor \frac{n}{3}\rfloor$ 的下标处的元素都等于该元素。

将数组 $\text{nums}$ 排序之后遍历数组 $\text{nums}$，对于下标 $i$，当 $i\ge \lfloor \frac{n}{3}\rfloor$ 时，如果 $\text{nums}[i]=\text{nums}[i-\lfloor \frac{n}{3}\rfloor ]$，则 $\text{nums}[i]$ 是出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 的元素。

为了避免重复计算，当 $i<n-1$ 且 $\text{nums}[i]=\text{nums}[i+1]$ 时跳过下标 $i$，只有当下标 $i$ 的右侧没有与 $\text{nums}[i]$ 相等的元素时才判断 $\text{nums}[i]=\text{nums}[i-\lfloor \frac{n}{3}\rfloor ]$ 是否成立，如果成立则将 $\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)$。摩尔投票算法可以推广到寻找出现次数大于 $\lfloor \frac{n}{k}\rfloor$ 的元素，其中 $k$ 是大于 $1$ 的正整数。

由于出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 的元素不可能超过 $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$。

遍历结束之后，得到两个候选元素。再次遍历数组，统计两个候选元素在数组中的出现次数，当出现次数大于 $\lfloor \frac{n}{3}\rfloor$ 时将候选元素添加到结果中。

代码

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)$。