[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)\)。
不需要额外空间，需要修改原始数组
方法四：标记法
标记法的思想和计数法是一致的，但这个方法比计数法，\(\texttt{Set}\) 更为巧妙。 考虑到数组元素值的范围是 \([1, n]\)，但数组长度为 \(n + 1\)，那么很显然在遍历数组的时候，我们将数组的值变为其对应的负数，那么再次遇到负数就得到了答案。1
2
3
4
5
6
7
8
9
10
11
12
13// Visited
public static int findDuplicate_mark(int[] nums) {
int len = nums.length;
for (int num : nums) {
int idx = Math.abs(num);
if (nums[idx] < 0) {
return idx;
}
nums[idx] = -nums[idx];
}
return len;
}
复杂度分析
- 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
- 空间复杂度：\(O(1)\)。
方法五：索引排序
索引排序是更难想到的方法。
数组排序之后，每个数组元素的值是其索引值 \(index + 1\)，那么就可以进行如此操作：
- 如果 \(\textit{nums}[i] == i + 1\)，说明已经排好序了，那么跳过，\(i++\)；
- 如果 \(\textit{nums}[i] == \textit{nums}[\textit{nums}[i] - 1]\)，说明在正确的索引已经有一个值了，那么这个值就是重复的元素；
- 上述均不满足，交换 \(\textit{nums}[i]\) 和 \(\textit{nums}[\textit{nums}[i] - 1]\) 的值。
1 | // Index Sort |
复杂度分析
- 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
- 空间复杂度：\(O(1)\)。
不需要额外空间，不修改原始数组
方法六：暴力2重循环
如果不允许额外空间，不允许修改原始数组，大多数人反而不会想到这个方法。
这个方法会超时。1
2
3
4
5
6
7
8
9
10
11
12
13// 2 Loops
public static int findDuplicate_2loops(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
return len;
}
复杂度分析
- 时间复杂度：\(O(n^2)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
- 空间复杂度：\(O(1)\)。
方法七：二分搜索
这里感谢大神 @liweiwei1419 的 详细题解 ，大家可以参考他的详细题解进行理解。
二分搜索是用来在有序数组里查找某个特定的值，但是这个数组并不是有序的，咋一看不适合使用二分搜索算法。
因为题目中规定了数组里元素大小在 \([1, n]\) 之间，而在 \([1, n]\) 之间找一个整数，并不是在输入数组中查找某个整数，所以这道题可以使用二分查找。
二分查找的思路是先猜一个数（在有效范围 \([\textit{left}, \textit{right}]\) 里位于中间的数 \(\textit{mid}\)），那么这个中间数和哪个数进行比较呢？
如果目标数 \(\textit{target}\) 小于 \(\textit{mid}\)，那么统计原始数组，小于等于 \(\textit{mid}\) 的元素的个数 \(\textit{cnt}\)，\(cnt \gt mid\)，反之 \(cnt \leq mid\) 。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23// Binary Search
public static int findDuplicate_bs(int[] nums) {
int len = nums.length;
int low = 1;
int high = len - 1;
while (low < high) {
int mid = low + (high - low) / 2;
int cnt = 0;
for (int i = 0; i < len; i++) {
if (nums[i] <= mid) {
cnt++;
}
}
if (cnt <= mid) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
复杂度分析
- 时间复杂度：\(O(n \log n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。二分查找最多需要二分 \(O(\log n)\) 次，每次判断的时候需要 \(O(n)\) 遍历 \(\textit{nums}\) 数组求解小于等于 \(\textit{mid}\) 的数的个数，因此总时间复杂度为 \(O(n \log n)\)。
- 空间复杂度：\(O(1)\)。
方法八：位运算
具体证明及讲解可以参 @LeetCode-Solution 官方题解 。
简单来说，把数字转为二进制，那么其实只需要关注 \(1\) 的个数及位数。具体到第 \(i\) 位，我们统计 \(\textit{nums}\) 数组中二进制展开后第 \(i\) 位为 \(1\) 的数为 \(x\) 个，数字 \([1,n]\) 这 \(n\) 个数二进制展开后第 \(i\) 位为 \(1\) 的数有 \(y\) 个，那么很显然只有 \(x > y\) 的情况下，重复的数的第 \(i\) 位为 \(1\)。
分别把 \([1, n]\) 和数组数字的所有位为 \(1\) 统计出来，然后按位还原，即可得到这个重复的数。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// Bit
public static int findDuplicate_bit(int[] nums) {
int n = nums.length;
int ans = 0;
int bit_max = 31;
while (((n - 1) >> bit_max) == 0) {
bit_max -= 1;
}
for (int bit = 0; bit <= bit_max; ++bit) {
int x = 0, y = 0;
for (int i = 0; i < n; ++i) {
if ((nums[i] & (1 << bit)) != 0) {
x += 1;
}
if (i >= 1 && ((i & (1 << bit)) != 0)) {
y += 1;
}
}
if (x > y) {
ans |= 1 << bit;
}
}
return ans;
}
复杂度分析
时间复杂度：\(O(n \log n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。\(O(\log n)\) 代表了我们枚举二进制数的位数个数，枚举第 \(i\) 位的时候需要遍历数组统计 \(x\) 和 \(y\) 的答案，因此总时间复杂度为 \(O(n \log n)\)。
空间复杂度：\(O(1)\)。
方法九：双指针
具体讲解可以参考 官方题解 @kirsche 的题解 287.寻找重复数 。
简单来说，因为数组数字在 \([1, n]\)，而数组索引值 \([0, n]\)，那么数组就可以构成一个环形链表，我们可以使用 \(\textit{nums}[\textit{nums}[i]]\) 来表示 \(\textit{nums}[i]\).
那么问题就转化成了 142. 环形链表 II ，这里不多解释。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// Slow Fast Pointers
public static int findDuplicate_fastSlow(int[] nums) {
int slow = 0;
int fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
复杂度分析
- 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
- 空间复杂度：\(O(1)\)。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗