[LeetCode][287. 寻找重复数] 9种方法(可能是最全的),拓展思路!

By Long Luo

这篇文章是 287. 寻找重复数 的题解。

目前这道题,经过自己摸索和参考 官方题解: 寻找重复数 ,目前发现了9种方法。

这些方法可以分为以下几类:

  • 需要额外空间,需要修改原始数组 O(logn)O(logn) space
    • 排序 - O(nlogn)O(nlogn) time
  • 需要额外空间,不修改原始数组 O(n)O(n) space
    • 计数法 - O(n)O(n) time
    • Set - O(n)O(n) time
  • 不需要额外空间,需要修改原始数组 O(1)O(1) space
    • 标记法 - O(n)O(n) time
    • 索引排序 - O(n)O(n) time
  • 不需要额外空间,不修改原始数组 O(1)O(1) space
    • 暴力 - O(n2)O(n^2) time
    • 二分搜索 - O(nlogn)O(nlogn) time
    • 位运算 - O(nlogn) time
    • 双指针 - O(n)O(n) time

因为题目要求:

  1. 必须不修改数组 nums\textit{nums}
  2. 只用常量级 O(1)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(nlogn+n)O(nlogn + n),其中 nnnums\textit{nums} 数组的长度,O(logn)O(logn) 排序复杂度,总时间复杂度为 O(nlogn+n)O(nlogn + n)
  • 空间复杂度:O(logn)O(logn),排序需要使用 O(logn)O(logn) 空间。

需要额外空间,不修改原始数组

方法二:计数法

因为数组元素值的范围是 [1,n][1, n] 之间,那么可以使用一个数组来记录数字出现次数,次数大于 11 即为答案。

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)O(n),其中 nnnums\textit{nums} 数组的长度。
  • 空间复杂度:O(n)O(n),需要新建一个长度为 nn 的数组。

方法三: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)O(n),其中 nnnums\textit{nums} 数组的长度。
  • 空间复杂度:O(n)O(n)

不需要额外空间,需要修改原始数组

方法四:标记法

标记法的思想和计数法是一致的,但这个方法比计数法,Set\texttt{Set} 更为巧妙。
考虑到数组元素值的范围是 [1,n][1, n],但数组长度为 n+1n + 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)O(n),其中 nnnums\textit{nums} 数组的长度。
  • 空间复杂度:O(1)O(1)

方法五:索引排序

索引排序是更难想到的方法。

数组排序之后,每个数组元素的值是其索引值 index+1index + 1,那么就可以进行如此操作:

  1. 如果 nums[i]==i+1\textit{nums}[i] == i + 1,说明已经排好序了,那么跳过,i++i++
  2. 如果 nums[i]==nums[nums[i]1]\textit{nums}[i] == \textit{nums}[\textit{nums}[i] - 1],说明在正确的索引已经有一个值了,那么这个值就是重复的元素;
  3. 上述均不满足,交换 nums[i]\textit{nums}[i]nums[nums[i]1]\textit{nums}[\textit{nums}[i] - 1] 的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Index Sort
// n+1 numbers in n.
public static int findDuplicate_index_sort(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; ) {
int n = nums[i];
if (n == i + 1) {
i++;
} else if (n == nums[n - 1]) {
return n;
} else {
nums[i] = nums[n - 1];
nums[n - 1] = n;
}
}

return 0;
}

复杂度分析

  • 时间复杂度:O(n)O(n),其中 nnnums\textit{nums} 数组的长度。
  • 空间复杂度:O(1)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(n2)O(n^2),其中 nnnums\textit{nums} 数组的长度。
  • 空间复杂度:O(1)O(1)

方法七:二分搜索

这里感谢大神 @liweiwei1419详细题解 ,大家可以参考他的详细题解进行理解。

二分搜索是用来在有序数组里查找某个特定的值,但是这个数组并不是有序的,咋一看不适合使用二分搜索算法。

因为题目中规定了数组里元素大小在 [1,n][1, n] 之间,而在 [1,n][1, n] 之间找一个整数,并不是在输入数组中查找某个整数,所以这道题可以使用二分查找。

二分查找的思路是先猜一个数(在有效范围 [left,right][\textit{left}, \textit{right}] 里位于中间的数 mid\textit{mid}),那么这个中间数和哪个数进行比较呢?

如果目标数 target\textit{target} 小于 mid\textit{mid},那么统计原始数组,小于等于 mid\textit{mid} 的元素的个数 cnt\textit{cnt}cnt>midcnt \gt mid,反之 cntmidcnt \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(nlogn)O(nlogn),其中 nnnums\textit{nums} 数组的长度。二分查找最多需要二分 O(logn)O(logn) 次,每次判断的时候需要 O(n)O(n) 遍历 nums\textit{nums} 数组求解小于等于 mid\textit{mid} 的数的个数,因此总时间复杂度为 O(nlogn)O(nlogn)
  • 空间复杂度:O(1)O(1)

方法八:位运算

具体证明及讲解可以参 @LeetCode-Solution 官方题解

简单来说,把数字转为二进制,那么其实只需要关注 11 的个数及位数。具体到第 ii 位,我们统计 nums\textit{nums} 数组中二进制展开后第 ii 位为 11 的数为 xx 个,数字 [1,n][1,n]nn 个数二进制展开后第 ii 位为 11 的数有 yy 个,那么很显然只有 x>yx > y 的情况下,重复的数的第 ii 位为 11

分别把 [1,n][1, n] 和数组数字的所有位为 11 统计出来,然后按位还原,即可得到这个重复的数。

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(nlogn)O(nlogn),其中 nnnums\textit{nums} 数组的长度。O(logn)O(logn) 代表了我们枚举二进制数的位数个数,枚举第 ii 位的时候需要遍历数组统计 xxyy 的答案,因此总时间复杂度为 O(nlogn)O(nlogn)

  • 空间复杂度:O(1)O(1)

方法九:双指针

具体讲解可以参考 官方题解 @kirsche 的题解 287.寻找重复数

简单来说,因为数组数字在 [1,n][1, n],而数组索引值 [0,n][0, n],那么数组就可以构成一个环形链表,我们可以使用 nums[nums[i]]\textit{nums}[\textit{nums}[i]] 来表示 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)O(n),其中 nnnums\textit{nums} 数组的长度。
  • 空间复杂度:O(1)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. 😉😃💗