剑指Offer-题3-数组中重复的数字
题目：数组中重复的数字
题目一：找出数组中重复的数字
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的。但不知道有几个数字重复了，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
题目二：不修改数组找出数组中重复的数字
在一个长度为n+1的数组里的所有数字都在1~n的范围内。所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。
解析
解析题目一
数组在空间上连续且含有下标，此题考虑查找效率
稍加思索，决定利用下标：若数值与下标不同则与数值对应下标的数值进行置换，若置换中发现两数相同则查找结束，如此时间复杂度仅O(n)，代码如下1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18bool findDuplicate(int arr[], int length, int *duplication)
{
int temp;
for (int i = 0; i < length; ++i)
if (i != arr[i])
if (arr[i] != arr[arr[i]])
{
temp = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = temp;
}
else
{
*duplication = arr[i];
return true;
}
return false;
}
对照书本发现思路相同，nice !😎
原来无意中已利用下标充当Hash Table(哈希表)的思想解决了问题
不过本人漏掉重要的空值检测、边界检测😭，修复代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23bool findDuplicate(int arr[], int length, int *duplication)
{
if (arr == nullptr || length <= 0)
return false;
for (int i = 0; i < length; ++i)
if (arr[i] >= length || arr[i] < 0)
return false;
int temp;
for (int i = 0; i < length; ++i)
if (i != arr[i])
if (arr[i] != arr[arr[i]])
{
temp = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = temp;
}
else
{
*duplication = arr[i];
return true;
}
return false;
}
原本以为完美无瑕，测试数组{0,2,0}发现无法找出重复数字。
究其原因对于替换数值后的数组{0,0,2}未再次判断，导致第二位 0 成为漏网之鱼，下为书中神级代码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
26bool duplicate(int numbers[], int length, int *duplication)
{
if (numbers == nullptr || length <= 0)
return false;
for (int i = 0; i < length; ++i)
if (numbers[i] >= length || numbers[i] < 0)
return false;
int temp;
for (int i = 0; i < length; ++i)
// 使用while便无“漏网之0”
while (i != numbers[i])
{
if (numbers[i] != numbers[numbers[i]])
{
temp = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = temp;
}
else
{
*duplication = numbers[i];
return true;
}
}
return false;
}
解析题目二
禁止修改输入数组？呵！断我财路，emmmm。苦思冥想，仅想到拷贝数组套用题目一方法……1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22bool findDuplicate(int arr[], int length, int *duplication)
{
if (nullptr == arr || length <= 0)
return false;
for (int i = 0; i < length; ++i)
if (arr[i] >= length || arr[i] < 1)
return false;
int *arrTemp = new int[length - 1];
for (int i = 0; i < length - 1; ++i)
arrTemp[i] = -1;
for (int i = 0; i < length; ++i)
{
if (arrTemp[arr[i] - 1] == arr[i])
{
*duplication = arr[i];
return true;
}
arrTemp[arr[i] - 1] = arr[i];
}
delete arrTemp;
return false;
}
一筹莫展之下，阅读书中解析顿觉豁然开朗！书中指出，含重复数字范围内数字个数必大于该范围长度。例如
- 对于长度为3的数组{1,2,2}，范围[1,1]内的数字个数为1等于范围长度1，而范围[2,2]内的数字个数为2大于范围长度1，可以确定重复数字位于范围[2,2]中即为2。
- 对于长度为5的数组{2,2,3,4,4}，范围[1,2]内的数字个数为2等于范围长度2，而范围[3,4]内的数字个数为3大于范围长度2，可以确定重复数字位于范围[3,4]中。继续分析范围[3,3]内的数字个数为1等于范围长度1，而范围[4,4]内的数字个数为2大于范围长度1，可以确定重复数字位于范围[4,4]中即为4。(此方法对于多个重复数字仅能找到其中之一)
以上两例说明只需对计数范围不断二分法，必定能找出重复数字。因此写出书中神级代码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
39int countRange(int numbers[], int length, int start, int end)
{
if (nullptr == numbers)
return 0;
int count = 0;
for (int i = 0; i < length; ++i)
if (numbers[i] >= start && numbers[i] <= end)
++count;
return count;
}
bool duplicate(int numbers[], int length, int *duplication)
{
if (nullptr == numbers || length <= 0)
return false;
for (int i = 0; i < length; ++i)
if (numbers[i] >= length || numbers[i] < 1)
return false;
int start = 1;
int end = length - 1;
while (end >= start)
{
int middle = ((end - start) << 1) + start;
int count = countRange(numbers, length, start, middle);
if (end == start)
if (count > 1)
{
*duplication = start;
return true;
}
else
break;
if (count > (middle - start + 1))
end = middle;
else
start = middle + 1;
}
return false;
}
对于此二分查找法，countRange将被调用O(logn)次，而countRange的时间复杂度为O(n)，故总时间复杂度为O(nlogn)。空间复杂度为O(1)，这是利用时间换空间。
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可
