（LeetCodeHot100）169. 多数元素——majority-element

169. 多数元素——majority-element

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

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

示例 1：

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

示例 2：

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

提示：

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109
  • 输入保证数组中一定有一个多数元素。
  • 这题我想到的是既然既要存数字又要存出现次数，肯定得用一个类封装一下，里面有数字的值和出现次数：

我的错误代码（写不下去了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class elem {
    int appearTime = 0;
    int num;
    elem(int num) {
        this.num = num;
    }
    void addTime() {
        this.appearTime++;
    }
}
class Solution {
    public int majorityElement(int[] nums) {
        HashSet<elem> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            elem e = new elem(nums[i]);
            e.addTime();
            set.add(e);
        }
        Iterator<set> it = new Iterator<set>;
    }
}

  1. 自定义类elem的问题：

    你定义了elem类来记录元素值和出现次数，但没有重写equals()和hashCode()方法。这会导致HashSet无法正确判断两个elem对象是否代表同一个数字（比如两个值为 3 的elem会被视为不同对象），统计次数会完全错误。

  2. 逻辑错误：

    循环中每次都新建elem对象并直接加入集合，没有检查该数字是否已存在，导致每个元素都被当作新元素，无法累计次数。

  3. 迭代器使用错误：

    Iterator<set>语法错误（应为Iterator<elem>），且迭代器初始化方式错误，集合的迭代器需通过set.iterator()获取。

方法一：哈希表

思路

我们知道出现次数最多的元素大于 ⌊2/n⌋ 次，所以可以用哈希表来快速统计每个元素出现的次数。

算法

我们使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。

我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            } else {
                counts.put(num, counts.get(num) + 1);
            }
        }
        // 返回统计完成的映射表
        return counts;
    }

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums);

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.getKey();
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们遍历数组 nums 一次，对于 nums 中的每一个元素，将其插入哈希表都只需要常数时间。如果在遍历时没有维护最大值，在遍历结束后还需要对哈希表进行遍历，因为哈希表中占用的空间为 O(n)（可参考下文的空间复杂度分析），那么遍历的时间不会超过 O(n)。因此总时间复杂度为 O(n)。
  • 空间复杂度：O(n)。哈希表最多包含 n−⌊2/n⌋ 个键值对，所以占用的空间为 O(n)。这是因为任意一个长度为 n 的数组最多只能包含 n 个不同的值，但题中保证 nums 一定有一个众数，会占用（最少） ⌊2/n⌋+1 个数字。因此最多有 n−(⌊2/n⌋+1) 个不同的其他数字，所以最多有 n−⌊2/n⌋ 个不同的元素。

  • entrySet() 方法

    • Map 是一种存储键值对（Key-Value） 的数据结构（例如 {1:3, 2:4} 中，1 和 2 是键，3 和 4 是值）。

    • entrySet() 是 Map 接口中的一个方法，它的作用是：

    • 返回一个包含 Map 中所有键值对的集合（Set），集合中的每个元素都是一个 Map.Entry 对象。

    • 可以理解为：entrySet() 把 Map 中的每一对键值对 “拆成” 一个个独立的 Entry对象，再装进一个 Set 里，方便遍历所有键值对。

  • Map.Entry 接口（通常简称 entry）

    • Map.Entry 是 Map 内部定义的一个接口，用于表示 Map 中的一个键值对。

    • 它包含两个核心方法：

      • getKey()：返回当前键值对中的键（Key）。

      • getValue()：返回当前键值对中的值（Value）。

    • 可以把 Map.Entry 看作一个 “容器”，里面装着一对 Key 和 Value。

我的问题1

Map.Entry<Integer, Integer> majorityEntry = null;？Map的接口怎么可以实例化

这里的 Map.Entry<Integer, Integer> majorityEntry = null; 并不是在实例化 Map.Entry 接口，而是声明了一个接口类型的引用变量，并将其初始化为 null（表示暂时不指向任何对象）。

关键概念区分：

  1. 接口不能实例化：

    Map.Entry 是 Map 内部的一个接口（和 Map 一样，接口本身不能直接 new 出对象）。你不能写成 new Map.Entry<Integer, Integer>()，这会编译报错。

  2. 接口类型的引用变量可以指向实现类对象：

    虽然 Map.Entry 是接口，但 Map 的实现类（如 HashMap）内部会提供 Map.Entry 接口的具体实现（比如 HashMap 中的 Node 类，它实现了 Map.Entry 接口）。

    当你调用 counts.entrySet() 时，返回的 Set 集合中存储的元素，就是这些 “实现了 Map.Entry 接口的具体对象”（比如 HashMap$Node 实例）。

我的问题2

Map.Entry<Integer, Integer> entry : counts.entrySet()为什么Map.Entry可以指向Set对象

  • Set 是容器，里面装的是 Map.Entry 类型的元素。
  • 循环的过程是从 Set 容器中逐个取出元素，每个元素的类型是 Map.Entry，所以用 Map.Entry 类型的变量 entry 来接收。

类比：

就像 “String s : list”（list 是 List<String>），不是 “String 指向 List”，而是从 List 中取出 String 类型的元素给 s。

方法二：排序

思路

如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 ⌊2/n⌋ 的元素（下标从 0 开始）一定是众数。

算法

对于这种算法，我们先将 nums 数组排序，然后返回上文所说的下标对应的元素。下面的图中解释了为什么这种策略是有效的。在下图中，第一个例子是 n 为奇数的情况，第二个例子是 n 为偶数的情况。

image.png

对于每种情况，数组上面的线表示：如果众数是数组中的最小值时覆盖的下标，数组下面的线表示如果众数是数组中的最大值时覆盖的下标。对于其他的情况，这条线会在这两种极端情况的中间。对于这两种极端情况，它们会在下标为 ⌊2/n⌋ 的地方有重叠。因此，无论众数是多少，返回 ⌊2/n⌋ 下标对应的值都是正确的。

1
2
3
4
5
6
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

复杂度分析

  • 时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。
  • 空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。如果自己编写堆排序，则只需要使用 O(1) 的额外空间。

方法三：随机化

  1. 多数元素的 “占比特性”

题目里多数元素出现次数超过数组长度的一半（即超过 ⌊n/2⌋）。这意味着数组里超过一半的位置都是这个多数元素。

  1. 随机化的核心逻辑

既然超过一半的位置都是多数元素，那我们随机选一个数组下标，这个下标对应的元素 “很大概率” 就是多数元素。

  • 比如数组有 100 个元素，多数元素占了 51 个位置。那随机选一个下标，选到多数元素的概率超过 50%。
  • 要是第一次选的不是，就继续随机选，直到选到为止。
  1. 为什么效率不低？（期望次数分析）

你可能担心 “一直选不到怎么办”，但从概率期望的角度看，平均只需要选很少次：

  • 假设最坏情况（多数元素刚好占一半），第一次选对的概率是 1/2，第二次是 1/4（第一次错了，第二次对），第三次是 1/8…… 把这些 “次数 × 概率” 加起来，最终期望次数是 2 次（数学上可以证明这个求和的极限是 2）。
  • 每次选完后，只需要遍历数组（O(n) 时间）验证是否是多数元素。所以整体期望时间复杂度是 O(n)，效率很高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    private int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    public int majorityElement(int[] nums) {
        Random rand = new Random();

        int majorityCount = nums.length / 2;

        while (true) {
            int candidate = nums[randRange(rand, 0, nums.length)];
            if (countOccurences(nums, candidate) > majorityCount) {
                return candidate;
            }
        }
    }
}

方法四：分治

1. 分治的核心思想：“分而治之”

分治算法的思路是 “把大问题拆成小问题，解决小问题后合并结果”。对于本题，我们把原数组拆成左半部分和右半部分，分别找出两部分的 “局部众数”，再合并判断出整个数组的众数。

2. 多数元素的关键特性（反证法证明）

如果 a 是整个数组的众数，那么 a 至少是左半部分或右半部分的众数。

用反证法理解：

假设 a 既不是左半部分的众数，也不是右半部分的众数。

  • 左半部分长度为 l，则 a 在左半部分出现次数 ≤ l/2；
  • 右半部分长度为 r，则 a 在右半部分出现次数 ≤ r/2；
  • 那么 a 在整个数组的总出现次数 ≤ l/2 + r/2。
  • 但l + r 是数组总长度n，且l/2 + r/2 ≤ n/2（因为l + r = n），这与 “a是整个数组的众数（出现次数 >n/2）” 矛盾。因此，整个数组的众数一定是左或右半部分的众数。

3. 分治算法的执行流程

我们通过递归实现 “分而治之”：

  • 拆分（分）：把数组不断从中间拆成左、右两半，直到子数组长度为 1（此时子数组的唯一元素就是自己的众数）。
  • 合并（治）：
    • 如果左右子数组的众数相同，直接返回该众数；
    • 如果不同，统计两个众数在整个区间的出现次数，次数多的就是最终众数。

代码逻辑对应

  • majorityElementRec(nums, lo, hi)：递归函数，负责求解区间[lo, hi]的众数。
    • 递归终止条件：lo == hi（子数组长度为 1），返回该元素。
    • 拆分：计算中间位置 mid，递归求解左半部分 [lo, mid] 和右半部分 [mid+1, hi] 的众数 left 和 right。
    • 合并：
      • 若 left == right，直接返回；
      • 若不同，调用 countInRange 统计 left 和 right 在 [lo, hi] 的出现次数，返回次数多的那个。
  • countInRange(nums, num, lo, hi)：统计 num 在区间 [lo, hi] 内的出现次数，用于合并时判断最终众数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }

        // recurse on left and right halves of this slice.
        int mid = (hi - lo) / 2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid + 1, hi);

        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }

        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length - 1);
    }
}

复杂度分析（辅助理解）

  • 时间复杂度 O (nlogn)：每次递归将问题拆成两个子问题（规模减半），且每次合并需要遍历整个区间（线性时间）。根据主定理，最终时间复杂度为 O(nlogn)。
  • 空间复杂度 O (logn)：递归的深度由数组拆分次数决定（每次拆一半），最多拆 logn 次，因此栈空间复杂度为 O(logn)。

方法五：Boyer-Moore 投票算法

思路

如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

算法

Boyer-Moore 算法的本质和方法四中的分治十分类似。我们首先给出 Boyer-Moore 算法的详细步骤：

  • 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
  • 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
    • 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
    • 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
  • 在遍历完成后，candidate 即为整个数组的众数。

我们举一个具体的例子，例如下面的这个数组：

1
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

在遍历到数组中的第一个元素以及每个在 | 之后的元素时，candidate 都会因为 count 的值变为 0 而发生改变。最后一次 candidate 的值从 5 变为 7，也就是这个数组中的众数。

Boyer-Moore 算法的正确性较难证明，这里给出一种较为详细的用例子辅助证明的思路，供读者参考：

首先我们根据算法步骤中对 count 的定义，可以发现：在对整个数组进行遍历的过程中，count 的值一定非负。这是因为如果 count 的值为 0，那么在这一轮遍历的开始时刻，我们会将 x 的值赋予 candidate 并在接下来的一步中将 count 的值增加 1。因此 count 的值在遍历的过程中一直保持非负。

那么 count 本身除了计数器之外，还有什么更深层次的意义呢？我们还是以数组

1
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

作为例子，首先写下它在每一步遍历时 candidate 和 count 的值：

1
2
3
nums:      [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
candidate:  7  7  7  7  7  7   5  5   5  5  5  5   7  7  7  7
count:      1  2  1  2  1  0   1  0   1  2  1  0   1  2  3  4

我们再定义一个变量 value，它和真正的众数 maj 绑定。在每一步遍历时，如果当前的数 x 和 maj 相等，那么 value 的值加 1，否则减 1。value 的实际意义即为：到当前的这一步遍历为止，众数出现的次数比非众数多出了多少次。我们将 value 的值也写在下方：

1
2
nums:      [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
value:      1  2  1  2  1  0  -1  0  -1 -2 -1  0   1  2  3  4

有没有发现什么？我们将 count 和 value 放在一起：

1
2
3
nums:      [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
count:      1  2  1  2  1  0   1  0   1  2  1  0   1  2  3  4
value:      1  2  1  2  1  0  -1  0  -1 -2 -1  0   1  2  3  4

发现在每一步遍历中，count 和 value 要么相等，要么互为相反数！并且在候选众数 candidate 就是 maj 时，它们相等，candidate 是其它的数时，它们互为相反数！

为什么会有这么奇妙的性质呢？这并不难证明：我们将候选众数 candidate 保持不变的连续的遍历称为「一段」。在同一段中，count 的值是根据 candidate == x 的判断进行加减的。那么如果 candidate 恰好为 maj，那么在这一段中，count 和 value 的变化是同步的；如果 candidate 不为 maj，那么在这一段中 count 和 value 的变化是相反的。因此就有了这样一个奇妙的性质。

这样以来，由于：

  • 我们证明了 count 的值一直为非负，在最后一步遍历结束后也是如此；
  • 由于 value 的值与真正的众数 maj 绑定，并且它表示「众数出现的次数比非众数多出了多少次」，那么在最后一步遍历结束后，value 的值为正数；

在最后一步遍历结束后，count 非负，value 为正数，所以它们不可能互为相反数，只可能相等，即 count == value。因此在最后「一段」中，count 的 value 的变化是同步的，也就是说，candidate 中存储的候选众数就是真正的众数 maj。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

复杂度分析

  • 时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
  • 空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。