算法：找出数组中重复的数字

找出数组中重复的数字

描述：

在一个长度为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，则这个区间一定存在重复的数字；否则后半部分区间一定存在重复的数字。继续重复分割数字区间，直到找到一个重复的数字。

代码实践:

双重遍历

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("未找到");

排序+遍历

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("未找到");
}

哈希表+遍历

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、辅助数组+遍历

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、类似二分查找方法

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;
		}
		
	}
	
}