Fork me on GitHub

找出数组中重复的数字

这是崔斯特的第一百零八篇原创文章

努力、奋斗 (๑• . •๑)

找出数组中重复的数字

题目描述

在一个长度为 n 的数组里的所有数字都在 0n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为 7 的数组 {2, 3, 1, 0, 2, 5, 3},那么对应的输出是重复的数字 2 或者 3

解法

解法一

排序后,顺序扫描,判断是否有重复,时间复杂度为 O(n²)

解法二

利用哈希表,遍历数组,如果哈希表中没有该元素,则存入哈希表中,否则返回重复的元素。时间复杂度为 O(n),空间复杂度为 O(n)

解法三

长度为 n,元素的数值范围也为 n,如果没有重复元素,那么数组每个下标对应的值与下标相等。

从头到尾遍历数组,当扫描到下标 i 的数字 nums[i]

  • 如果等于 i,继续向下扫描;
  • 如果不等于 i,拿它与第 nums[i] 个数进行比较,如果相等,说明有重复值,返回 nums[i]。如果不相等,就把第 i 个数 和第 nums[i] 个数交换。重复这个比较交换的过程。

此算法时间复杂度为 O(n),因为每个元素最多只要两次交换,就能确定位置。空间复杂度为 O(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
27
28
29
30
31
32
33
34
/**
* @author zhujian on 2019/12/26.
*/
public class Solution {
public int findDuplicate(int[] array) {
if (array.length == 0) {
return -1;
}
for (int i = 0; i < array.length; i++) {
while (array[i] != i) {
if (array[i] == array[array[i]]) {
return array[i];
}
swap(array, i, array[i]);
System.out.println(Arrays.toString(array));
}
}
return -1;
}
private void swap(int[] array, int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
public static void main(String[] args) {
int[] arr = new int[]{2, 3, 1, 0, 2, 5, 3};
int res = new Solution().findDuplicate(arr);
System.out.println(res);
}
}

代码中有一个两重循环,但每个数字最多只要交换两次就可以找到属于自己的位置,因此时间复杂度是O(n)。不需要额外分配内存,空间复杂度是O(1)。

Output

1
2
3
4
[1, 3, 2, 0, 2, 5, 3]
[3, 1, 2, 0, 2, 5, 3]
[0, 1, 2, 3, 2, 5, 3]
2

以数组[2, 3, 1, 0, 2, 5, 3]为例来分析找到重复数字的步骤:

  1. 数组的第 0 个数字(从 0 开始计数,和数组的下标保持一致)是 2,与它的下标不相等,于是把它和下标为 2 的数字 1 交换。交换之后的数组是[1, 3, 2, 0, 2, 5, 3]。
  2. 此时第 0 个数字是 1,仍然与它的下标不相等,继续把它和下标为 1 的数字 3 交换,得到数组[3, 1, 2, 0, 2, 5, 3]
  3. 接下来继续交换第 0 个数字 3 和第 3 个数字 0,得到数组[0, 1, 2, 3, 2, 5, 3]。
  4. 此时第 0 个数字的数值为 0,接着扫描下一个数字。在接下来的几个数字中,下标为 1,2,3 的三个数字分别为 1,2,3 它们的下标和数值都分别相等,因此不需要做任何操作。
  5. 接下来扫描到下标为 4 的数字 2。由于它的数值与它的下标不相等,再比较它和下标为 2 的数字。注意到此时数组中下标为 2 的数字也是 2,也就是数字在下标为 2 和下标为 4 的两个位置都出现了,因此找到一个重复的数字。

本题关键是:在一个长度为 n 的数组里的所有数字都在 0n-1 的范围内并且有重复,这说明数组是可以排序的,把每个数字交换到自己应该在的位置,排序时就能找到重复字段。理想状态下的情况:[0, 1, 2, 3, 4, x, x, x]

Python解法更简单

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(arr):
if len(arr) == 0:
return -1
for i in range(len(arr)):
while arr[i] != i:
tmp = arr[i]
if tmp == arr[tmp]:
return tmp
arr[i], arr[tmp] = arr[tmp], arr[i]
print(arr)
print(solution([3, 1, 2, 0, 2, 5, 3]))

不修改数组找出重复的数字

题目描述

在一个长度为 n+1 的数组里的所有数字都在 1n 的范围内,数组中至少有一个数字是重复的,请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为 8 的数组 {2, 3, 5, 4, 3, 2, 6, 7},那么对应的输出是重复的数字 2 或者 3

解法

解法一

创建长度为 n+1 的辅助数组,把原数组的元素复制到辅助数组中。如果原数组被复制的数是 m,则放到辅助数组第 m 个位置。这样很容易找出重复元素。空间复杂度为 O(n)

解法二

数组元素的取值范围是 [1, n],对该范围对半划分,分成 [1, middle], [middle+1, n]。计算数组中有多少个(count)元素落在 [1, middle] 区间内,如果 count 大于 middle,那么说明这个范围内有重复元素,否则在另一个范围内。继续对这个范围对半划分,继续统计区间内元素数量。

时间复杂度 O(n * log n),空间复杂度 O(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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* @author zhujian on 2019/12/26.
*/
public class Solution {
public int findDuplicate(int[] array) {
if (array.length == 0) {
return -1;
}
int start = 1;
int end = array.length - 1;
while (start <= end) {
int middle = start + ((end - start) >> 1);
int count = countRange(array, start, middle);
if (end == start) {
if (count > 1) {
return start;
} else {
break;
}
} else {
if (count > (middle - start) + 1) {
end = middle;
} else {
start = middle + 1;
}
}
}
return -1;
}
private int countRange(int[] array, int start, int end) {
if (array.length == 0) {
return -1;
}
int count = 0;
for (int i : array) {
if (i >= start && i <= end) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int[] arr = new int[]{2, 3, 5, 4, 3, 2, 6, 7};
int res = new Solution().findDuplicate(arr);
System.out.println(res);
}
}

按照二分法查找的思路,如果输出长度为n的数组,那么函数countRange将被调用O(log n)次,每次需要O(n)时间,因此总的时间复杂度是O(nlog n) ,空间复杂度是O(1)