题目
https://www.nowcoder.com/questionTerminal/623a5ac0ea5b4e5f95552655361ae0a8
题意
在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是2或3。
题解
- 解法一：排序判断相邻的数字是否相等。时间复杂度O(NLogN)，空间复杂度O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
sort(numbers,numbers+length);
for(int i=1;i<length;i++){
if(numbers[i]==numbers[i-1]){
duplication[0]=numbers[i];
return true;
}
}
return false;
}
}; - 解法二：用hash表存每个数字出现的次数，当一个数字出现的次数大于1时，返回结果。时间复杂度O(N)，空间复杂度O(N)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
unordered_map<int,int> cnt;
for(int i=0;i<length;i++){
cnt[numbers[i]]++;
if(cnt[numbers[i]]>1){
duplication[0] = numbers[i];
return true;
}
}
return false;
}
}; - 解法三：给出的数都是1~N之间的数，所以如果我们将数组重排是的每个数都回到自己的位置上，即 i=numbers[i] ,如果有重复数字，则必定有数字在多个位置出现。
重排数组对每个数字numbers[i]，如果i=numbers[i]，则表示已经满足条件，继续下一个，如果不等于比较numbers[ numbers[i] ]和numbers[i] ，如果相等，则找到重复的数字，如果不相等，则交换numbers[i]和numbers[ numbers[i] ]，此时numbers[i] 位置上已经归位，继续比较交换过来的数字，直到找到重复数字或者i=numbers[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
21class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
for(int i=0;i<length;i++){
while(numbers[i]!=i){
if(numbers[i]==numbers[numbers[i]]){
duplication[0]=numbers[i];
return true;
}
swap(numbers[i],numbers[numbers[i]]);
}
}
return false;
}
};扩展题目
在一个长度为 n+1 的数组里的所有数字都在1到n的范围内。 所以数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改输入的数组。题解
- 上述解法一仍然适用，只不过需要增加O(N)的空间复杂度用来存储辅助数组，存放原数组的副本。
- 解法二也仍然适用。复杂度不变。
- 解法三也可以，同样需要O(N)的辅助空间。实际上，由于不能原来的数组，可以直接在复制到辅助数组时，便将其放到对应的位置上，如果有发现该位置已经有数字，则找到重复数字。时间杂度O(N)，空间复杂度O(N)。
- 如何能达到O(1)空间呢？不能用哈希表存数字出现的次数，我们只能计算每个数时，都对全数组扫描一遍，这样是O(N*N)时间复杂度+O(1)空间复杂度。还有优化余地吗？实际上我们可以发现，如果1~m之间的数的个数超过m，则必定有重复的数字（鸽巢原理），这样我们可以利用二分法，将范围不断缩小。直到范围为1。时间复杂度O(NLogN)，空间复杂度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
30class Solution {
public:
bool duplicate(int numbers[], int length, int* duplication) {
int left = 1,right = length-1;
while(left<=right){
int mid = (left+right)/2;
int count = getCount(numbers,length,left,mid);
if(left==right){
if(count>1){
duplication[0]=left;
return true;
}
}
if(count>(mid-left+1))
right=mid;
else
left=mid+1;
}
return false;
}
int getCount(int *numbers,int length,int left,int end)
{
int count=0;
for(int i=0;i<length;i++){
if(numbers[i]>=left&&numbers[i]<=end)
count++;
}
return count;
}
};