數組中重複的數字

02-12

數組中重複的數字

找出數組中重複的數字
在一個長度為n的數組裡的所有數組都在0～n-1的範圍。數組中某些數字是重複的，
但不知道有哪些數字重複了，也不知道每個數字重複了幾次。請找出數組中任意一個重複數字。

因為數組大小為n且元素在0~n-1，所以排序之後每個位置對應下標是自己的序號
基於排序，調整array[i] = i，
如果array[i] != i，觀察array[i] == array[array[i]]是否成立，成立則找到了。

否則，交換。

參考答案：

#include <stdio.h>#include <stdbool.h>void swap(int* a,int* b){int c=0;c=*a;*a=*b;*b=c;}bool duplicate(int array[],int length,int* duplication){if(array==NULL || length<=0) return false;for(int i=0;i<length;i++){ if(array[i]<0 || array[i]>length-1) return false;}for(int i=0;i<length;i++){ while(array[i] != i) { if(array[i] == array[array[i]]) { *duplication = array[i]; return true; } swap(&array[i],&array[array[i]]); }}return false;}int main(){int array[7]={2,3,1,0,2,5,3};bool isTrue = false;int duplication = -1;isTrue = duplicate(array,7,&duplication);printf("isTrue=%d duplication=%d ",isTrue,duplication);return 0;}

不修改數組找出重複的數字
在長度為n+1的數組裡的所有數字都在1~n的範圍，必有至少一個重複數字，
找出任意一個重複數字，但是不能修改數組。

二分查找思想
將1~n分成2部分，1~m的數字個數超過m，則其中一定有元素重複，m+1~n的數字個數超過n-m個，則其中一定有元素重複

參考代碼：

#include <stdio.h>int countRange(const int* array,int length,int begin,int end){ if(array == NULL) return 0; int count = 0; for(int i=0;i<length;i++) { if(array[i]>=array[begin] && array[i]<= array[end]) ++count; } return count;}int duplication(const int* array,int length){if(array == NULL || length < 0) return -1;int begin=1;int end = length-1;while(end >= begin){ int mid = begin + (end - begin)/2; int count = countRange(array,length,begin,mid); if(end == begin) { if(count>1) return array[begin]; else break; } if(count > (mid-begin+1)) end = mid; else begin = mid+1;}return -1;}int main(){int array[8] = {2,3,5,4,3,2,6,7};int num = 0;num = duplication(array,8);printf("%d ",num);return 0;}