找出数组中重复的数字

描述:

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

分析:

从数组中找出重复的数字,如果没有提示!

思路:

遍历数组进行匹配,考虑时间复杂度问题。

方案:

1、双重遍历

将数组中的每一个数与其他数做匹配,如果两者相等,输出,否则输出未找到提示。

2、排序+遍历

将数组排序,匹配相邻者数字,如果两者相等,输出,否则输出未找到提示。

3、哈希表+遍历

将遍历时的每个数存入哈希表中,每次存入的时候判断下是否

4、辅助数组+遍历

创建一个辅助数组,然后逐一把原数组的每个数字复制到辅助数组中,如果原数组中被复制的数字是n,则把它复制到辅助数组中下标为n的位置。如果该位置已有相同的数字,则该数字为重复数字。该方案需要O(n)的辅助空间。

5、类似二分查找方法

前提:在一个长度为n的数组里的所有数字都在0~n-1的范围内。我们把从0~n-1的数字从中间的数字【 (n-1)/2】(下面以m表示)分为两部分,前半部分为0~m,后半部分为m+1 ~ n-1。如果1~m的数字个数超过m,则这个区间一定存在重复的数字;否则后半部分区间一定存在重复的数字。继续重复分割数字区间,直到找到一个重复的数字。

代码实践:

双重遍历

1
2
3
4
5
6
7
8
9
10
11
12
int arr[] = {2,3,1,0,2,5,3};
int len = (int) sizeof(arr) / sizeof(*arr);
for (int i = 0;i<len;i++) {
int number = arr[i];
for (int j = i;j<len;j++) {
if (number == arr[j]) {
printf("%d",number);
return;
}
}
}
printf("未找到");

排序+遍历

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
int arr[] = {2,3,1,0,2,5,3};
int len = (int) sizeof(arr) / sizeof(*arr);

//排序
int i,j,temp;
for (i=1;i<len;i++){
temp = arr[i];
for (j=i;j>0 && arr[j-1]>temp;j--){
arr[j] = arr[j-1];
}
arr[j] = temp;
}

//遍历
int index = 0;
bool result = false;
for (int i = 0;i<len-1;i++) {
int number = arr[index];
int next = arr[index+1];
if (number == next) {
result = true;
printf("--%d---",number);
}
index = index+1;
}

if(result == false){
printf("未找到");
}

哈希表+遍历

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
int arr[] = {2,3,1,0,2,5,3};
int len = (int) sizeof(arr) / sizeof(*arr);

if(len <= 0 ){
return;
}


for(int i = 0; i < len ; i++){
if (arr[i] < 0 || arr[i] > len-1 ) {
return;
}
int number = arr[i];



while(number != i){
int nextNum = arr[number];
if(number == nextNum){
printf("%d",number);
break;
}
int temp = number;
arr[i] = nextNum;
arr[number] = temp;
}
}

4、辅助数组+遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
int arr[] = {2,3,1,0,2,5,3};
int len = (int) sizeof(arr) / sizeof(*arr);

int arr1[len+1];
for (int i = 0;i<len;i++) {
int number = arr[i];
int tagerNumber = arr1[number];
if(number == tagerNumber){
printf("----%d\n",number);
}else{
arr1[number] = number;
}
}

5、类似二分查找方法

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
int arr[] = {2,3,1,0,2,5,3};
int len = (int) sizeof(arr) / sizeof(*arr);

int start = 0;
int end = len;

while(start <= end){
int middle = (end+start)/2;
int count = 0;
//计算区间里的数字数目
for (int i = 0;i<len;i++) {
if(arr[i]<=middle && arr[i]>=start){
count++;
}
}

//如果区间内的数字个数大于区间的应有个数(比如:10-20, 中间数为15,区间为10-15,区间内应有5个数)
if (count > middle-start+1) {
//说明重复数字在[start,middle]中
end = middle;
}else{
//说明重复数字在[middle,end]中
start = middle+1;
}

//二分查找索引相遇代表查找结束。
if(end == start){
//count大于0,说明找到重复数字
if(count > 1){
printf("%d",start);
break;
}else{
break;
}

}

}