在長度為n+1的數組里的所有數字都在1~n的范圍內，所以數組中至少有一個數字是重復的。請找出數組中任意一個重復的數字，但不能修改輸入的數組。

思路：

一、把1~n的數字從中間的數字m分成兩部分，前面一半為1 ~m,后面一半為m+1 ~ n；
二、若1 ~ m的數字的數目超過m，那么這一半的區間里一定包含重復的數字；否則另 一半m+1 ~n的區間里一定包含重復的數字。
三、繼續把包含重復數字的區間一分為二，直到找到一個重復的數字。

時間復雜度：O(nlog(n)) 空間復雜度：O(1) #include <iostream> using namespace std;int countRange(const int* nums,int len,int start,int end){if(nums==nullptr) return 0;int count=0;for(int ii=0;ii<len;ii++){if(nums[ii]>=start&&nums[ii]<=end) count++;}return count; }int getDuplication(const int* nums,int len){if(nums==nullptr||len<=0) return -1;for(int ii=0;ii<len;ii++){if(nums[ii]<1||nums[ii]>len-1){return -1;}}int start=1;int end=len-1;while(end>=start){int mid=((end-start)>>1)+start;//找出中間元素int count=countRange(nums,len,start,mid);if(start==end){if(count>1) return start;else break;}if(count>(mid-start+1)){ //mid-start+1 意味著計算區間內元素的個數end=mid;}else{start=mid+1;}}return -1; }int main(){//int nums[]={2,3,5,4,7,2,6,7,7};int nums[]={1,1,9};int res=getDuplication(nums,sizeof(nums)/sizeof(int));cout<<res<<endl; }

總結

以上是生活随笔為你收集整理的不修改数组找出重复的数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。