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

LeetCode题练习与总结：多数元素 Ⅱ--229

news 2024/11/16 7:26:01

一、题目描述

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

二、解题思路

这个问题可以使用摩尔投票法来解决。摩尔投票法的核心思想是通过投票的方式来找到可能超过 ⌊ n/k ⌋ 次的元素，其中 k 是要求的众数个数。在这个问题中，k=3，因此最多可能有2个出现次数超过 ⌊ n/3 ⌋ 的元素。

以下是摩尔投票法的步骤：

初始化两个候选元素（candidate1 和 candidate2）和它们对应的计数（count1 和 count2）。
遍历数组，对于数组中的每个元素：
- 如果它是 candidate1，则 count1 加一。
- 如果它是 candidate2，则 count2 加一。
- 如果 count1 为 0，则将当前元素设为 candidate1，并将 count1 置为 1。
- 如果 count2 为 0，则将当前元素设为 candidate2，并将 count2 置为 1。
- 如果它不是 candidate1 也不是 candidate2，则将 count1 和 count2 各减一。
遍历结束后，candidate1 和 candidate2 可能是出现次数超过 ⌊ n/3 ⌋ 的元素，但还需要再次遍历数组来确认它们的实际出现次数。
最后，将出现次数确实超过 ⌊ n/3 ⌋ 的元素添加到结果列表中。

三、具体代码

import java.util.ArrayList;
import java.util.List;class Solution {public List<Integer> majorityElement(int[] nums) {List<Integer> result = new ArrayList<>();if (nums == null || nums.length == 0) return result;int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;// 遍历数组，寻找可能的候选人for (int num : nums) {if (num == candidate1) {count1++;} else if (num == candidate2) {count2++;} else if (count1 == 0) {candidate1 = num;count1 = 1;} else if (count2 == 0) {candidate2 = num;count2 = 1;} else {count1--;count2--;}}// 重新计数以确认候选人的出现次数count1 = 0;count2 = 0;for (int num : nums) {if (num == candidate1) count1++;else if (num == candidate2) count2++;}// 将出现次数超过 n/3 的元素添加到结果列表中if (count1 > nums.length / 3) result.add(candidate1);if (count2 > nums.length / 3) result.add(candidate2);return result;}
}

这段代码首先初始化两个候选人和对应的计数器，然后遍历数组进行投票。在投票阶段结束后，再次遍历数组以确认候选人的出现次数是否真的超过 ⌊ n/3 ⌋。最后，将满足条件的候选人添加到结果列表中。

四、时间复杂度和空间复杂度

1. 时间复杂度

第一个for循环遍历整个数组，这个操作的时间复杂度是O(n)，其中n是数组nums的长度。
第二个for循环也是遍历整个数组，同样具有O(n)的时间复杂度。

两个for循环是顺序执行的，因此总的时间复杂度是O(n) + O(n) = O(2n)。在时间复杂度分析中，我们通常忽略常数因子，因此最终的时间复杂度是O(n)。

2. 空间复杂度

我们使用了几个整型变量（candidate1, candidate2, count1, count2），这些变量占用的空间是常数，因此它们的空间复杂度是O(1)。
我们还使用了一个列表result来存储结果。在最坏的情况下，如果数组中的所有元素都是出现次数超过n/3的元素，那么列表的大小将是2（因为最多只有两个这样的元素）。因此，列表result的空间复杂度也是O(1)。

综上所述，整个算法的空间复杂度是O(1)，因为我们没有使用与输入数组大小成比例的额外空间。这意味着算法的空间效率是非常高的，因为它只需要固定的额外空间，而不依赖于输入数据的大小。

五、总结知识点

类定义：
- class 关键字用于定义一个类。
- 类名通常以大写字母开头。
方法定义：
- public 关键字指定方法的访问权限，允许其他类访问这个方法。
- List<Integer> 表示方法返回一个整数列表。
数组：
- int[] nums 定义了一个整型数组作为方法的参数。
条件语句：
- if 语句用于条件判断。
- else if 语句用于处理多个条件。
- else 语句用于处理所有其他情况。
循环：
- for 循环用于遍历数组中的每个元素。
列表操作：
- List<Integer> 定义了一个整数列表。
- ArrayList<Integer> 是 List 接口的一个实现，用于创建列表实例。
- result.add(candidate1) 方法用于向列表中添加元素。
变量：
- int 类型用于定义整数变量。
- 变量用于存储和操作数据。
算法逻辑：
- 摩尔投票法（Boyer-Moore Voting Algorithm）用于寻找可能超过特定阈值的元素。
- 通过两个候选人（candidate1 和 candidate2）和它们的计数器（count1 和 count2）来实现算法。
数学运算：
- nums.length / 3 用于计算数组长度除以3的整数部分，即计算阈值。
逻辑运算：
- > 用于比较两个数的大小。