当前位置：首页 > article >正文

多数元素问题

article 2024/10/20 16:26:31

多数元素

问题描述

给定一个大小为 n 的整数数组 nums，需要找出其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。可以假设数组是非空的，并且一定存在多数元素。

示例

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

示例 2：

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

解题思路

为了高效地找出数组中的多数元素，可以使用 Boyer-Moore 投票算法。该算法的核心思想是：

候选人（candidate）：假设数组中的某个元素是多数元素。
计数器（count）：用于统计当前候选人出现的次数。

算法步骤如下：

初始化
- candidate 设为 null。
- count 设为 0。
遍历数组
- 对于数组中的每个元素 num：
  - 如果 count == 0，则将 candidate 设置为当前的 num。
  - 如果 num == candidate，则 count++。
  - 否则，count--。
返回结果
- 遍历结束后，candidate 即为多数元素。

为什么这个算法有效？

由于多数元素出现的次数大于 n/2，因此多数元素和其他元素的数量差至少为 1。
算法的过程实际上是在抵消多数元素和非多数元素，最后剩下的就是多数元素。

代码解释

function majorityElement(nums: number[]): number {
    let count = 0;
    let candidate: number | null = null;

    for (let num of nums) {
        if (count === 0) {
            candidate = num; // 当计数为 0，假设当前元素为候选人
        }
        count += (num === candidate) ? 1 : -1; // 如果是候选人，计数加 1，否则减 1
    }

    return candidate!;
}

变量初始化：
- let count = 0;：初始化计数器为 0。
- let candidate: number | null = null;：初始化候选人为 null。
遍历数组：
```
for (let num of nums) { ... }
```
- 当 count == 0 时：
```
if (count === 0) {
    candidate = num;
}
```
  - 说明之前的候选人已经被抵消，需要重新假设当前元素为候选人。
- 更新计数器：
```
count += (num === candidate) ? 1 : -1;
```
  - 如果当前元素等于候选人，计数器加 1。
  - 如果不等，计数器减 1。
返回结果：
```
return candidate!;
```
- TypeScript 中 candidate 可能为 null，但根据题意，数组一定存在多数元素，所以在这里可以使用非空断言 !。

示例演示

以数组 [2,2,1,1,1,2,2] 为例：

初始化：
- count = 0
- candidate = null
遍历过程：
1. num = 2
  - count == 0，所以 candidate = 2
  - num == candidate，所以 count = 1
2. num = 2
  - num == candidate，count = 2
3. num = 1
  - num != candidate，count = 1
4. num = 1
  - num != candidate，count = 0
5. num = 1
  - count == 0，candidate = 1
  - num == candidate，count = 1
6. num = 2
  - num != candidate，count = 0
7. num = 2
  - count == 0，candidate = 2
  - num == candidate，count = 1
结果：
- 最终 candidate = 2，所以返回 2。

时间和空间复杂度分析

时间复杂度：
- 遍历一次数组，时间复杂度为 O(n)，其中 n 是数组的长度。
空间复杂度：
- 使用了常数级别的额外空间，空间复杂度为 O(1)。

其他解法

除了 Boyer-Moore 投票算法，还有其他解法，但相对效率较低：

哈希表统计法：
- 使用哈希表统计每个元素出现的次数。
- 当某个元素的计数超过 n/2 时，返回该元素。
- **时间复杂度：**O(n)
- **空间复杂度：**O(n)
排序法：
- 将数组排序。
- 由于多数元素出现次数超过 n/2，所以排序后，位于中间位置的元素必定是多数元素。
- **时间复杂度：**O(n log n)
- **空间复杂度：**取决于排序算法，通常为 O(1)（原地排序）或 O(n)

为什么选择 Boyer-Moore 投票算法？

高效性：
- 时间复杂度为 O(n)，且空间复杂度为 O(1)，非常高效。
简洁性：
- 实现简单，代码简洁明了。
题目要求：
- 题目假设数组一定存在多数元素，满足算法的前提条件。

注意事项

保证多数元素存在：
- 该算法假设多数元素一定存在。如果有可能不存在多数元素，则在算法结束后需要再次验证 candidate 是否确实为多数元素。
TypeScript 非空断言：
- 在返回 candidate 时使用了 !，表示我们确信 candidate 不为 null。

测试代码

function testMajorityElement() {
    const testCases = [
        { nums: [3, 2, 3], expected: 3 },
        { nums: [2, 2, 1, 1, 1, 2, 2], expected: 2 },
        { nums: [1], expected: 1 },
        { nums: [6, 5, 5], expected: 5 },
    ];

    for (let { nums, expected } of testCases) {
        const result = majorityElement(nums);
        console.assert(result === expected, `测试失败：输入 ${nums}，期望输出 ${expected}，实际输出 ${result}`);
    }

    console.log("所有测试用例通过！");
}

testMajorityElement();