給出一個(gè)數(shù)組 nums 包含 n + 1 個(gè)整數(shù)，每個(gè)整數(shù)是從 1到 n (包括邊界)，保證至少存在一個(gè)重復(fù)的整數(shù)。假設(shè)只有一個(gè)重復(fù)的整數(shù)，找出這個(gè)重復(fù)的數(shù)。

 注意事項(xiàng)

1.不能修改數(shù)組(假設(shè)數(shù)組只能讀)
2.只能用額外的O(1)的空間
3.時(shí)間復(fù)雜度小于O(n^2)
4.數(shù)組中只有一個(gè)重復(fù)的數(shù)，但可能重復(fù)超過(guò)一次

創(chuàng)新互聯(lián)是專業(yè)的川匯網(wǎng)站建設(shè)公司，川匯接單;提供成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行川匯網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!   樣例

給出 nums = [5,5,4,3,2,1]，返回 5.
給出 nums = [5,4,4,3,2,1]，返回 4.

 1   int findDuplicate(vector &nums) {
 2 // write your code here 3 int left=1,right=nums.size()-1;
 4 int mid=left+(right-left)/2;
 5 int left_num;
 6 while(left

自己沒(méi)想出來(lái)，照著網(wǎng)上的思路寫(xiě)了一個(gè)

left是1，right是n。mid算出來(lái)以后遍歷數(shù)組，看有多少小于等于它的，如果統(tǒng)計(jì)的數(shù)量小于等于mid這個(gè)數(shù)的本身，就說(shuō)明重復(fù)的數(shù)在比mid大的那邊。

于是就left＝mid＋1（因?yàn)椴粔蚵锼圆灰耍┗蛘遰ight＝mid。最后left＝right的值就是所求


本文名稱：633.尋找重復(fù)的數(shù)-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)網(wǎng)址：http://weahome.cn/article/cdhcds.html