[LeetCode][287. 寻找重复数] 9种方法(可能是最全的)，拓展思路!
By Long Luo
这篇文章是 287. 寻找重复数 的题解。
目前这道题，经过自己摸索和参考 官方题解: 寻找重复数 ，目前发现了9种方法。
这些方法可以分为以下几类：
- 需要额外空间，需要修改原始数组 \(O(\log n)\) space
- 排序 - \(O(n \log n)\) time
- 需要额外空间，不修改原始数组 \(O(n)\) space
- 计数法 - \(O(n)\) time
- Set - \(O(n)\) time
- 不需要额外空间，需要修改原始数组 \(O(1)\) space
- 标记法 - \(O(n)\) time
- 索引排序 - \(O(n)\) time
- 不需要额外空间，不修改原始数组 \(O(1)\) space
- 暴力 - \(O(n^2)\) time
- 二分搜索 - \(O(n \log n)\) time
- 位运算 - O(n n) time
- 双指针 - \(O(n)\) time
因为题目要求：
- 必须不修改数组 \(\textit{nums}\)；
- 只用常量级 \(O(1)\) 的额外空间。
因此我们先从需要修改数组的方案开始，下面我们就来一一分析：
需要额外空间，需要修改原始数组
方法一：排序
先对数组进行排序，然后遍历数组，如果出现重复数字既是答案。1
2
3
4
5
6
7
8
9
10
11
12// Sort
public static int findDuplicate_sort(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
for (int i = 1; i < len; i++) {
if (nums[i] == nums[i - 1]) {
return nums[i];
}
}
return len;
}
复杂度分析
- 时间复杂度：\(O(n \log n + n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度，\(O(\log n)\) 排序复杂度，总时间复杂度为 \(O(n \log n + n)\)。
- 空间复杂度：\(O(\log n)\)，排序需要使用 \(O(\log n)\) 空间。
需要额外空间，不修改原始数组
方法二：计数法
因为数组元素值的范围是 \([1, n]\) 之间，那么可以使用一个数组来记录数字出现次数，次数大于 \(1\) 即为答案。1
2
3
4
5
6
7
8
9
10
11
12
13// Count
public static int findDuplicate_count(int[] nums) {
int len = nums.length;
int[] cnt = new int[len + 1];
for (int i = 0; i < len; i++) {
cnt[nums[i]]++;
if (cnt[nums[i]] > 1) {
return nums[i];
}
}
return len;
}
复杂度分析
- 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
- 空间复杂度：\(O(n)\)，需要新建一个长度为 \(n\) 的数组。
方法三：HashSet
同方法二，这里使用HashSet来记录数组元素。1
2
3
4
5
6
7
8
9
10
11
12// Set
public static int findDuplicate_set(int[] nums) {
Set<Integer> set = new HashSet<>();
int len = nums.length;
for (int i = 0; i < len; i++) {
if (!set.add(nums[i])) {
return nums[i];
}
}
return len;
}
复杂度分析
- 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
- 空间复杂度：\(O(n)\)。