2-數(shù)組中重復(fù)的數(shù)字

一、問(wèn)題描述: 找出數(shù)組中重復(fù)的數(shù)字
在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0~n-1的范圍內(nèi)，數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)，也不知道重復(fù)了幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。

• 排序
• 哈希表。從頭到尾按順序掃描數(shù)組的每個(gè)數(shù)字，每掃描到一個(gè)數(shù)字，都可以用O(1)的時(shí)間來(lái)判斷哈希表里是否已經(jīng)包含了該數(shù)字。如果哈希表里還沒(méi)有這個(gè)數(shù)字，就把它加入哈希表，如果哈希表里已經(jīng)存在該數(shù)字，就找到一個(gè)重復(fù)的數(shù)字。這個(gè)算法的時(shí)間復(fù)雜度是O(n)，但它提高時(shí)間效率是以一個(gè)大小為O(n)的哈希表為代價(jià)的
• 重排數(shù)組。數(shù)組元素都在0~n-1之間，如果這個(gè)數(shù)組沒(méi)有重復(fù)的數(shù)字，那么當(dāng)數(shù)組排序之后數(shù)字i會(huì)出現(xiàn)在下標(biāo)為i的位置。從頭到尾依次掃描這個(gè)數(shù)組中的每個(gè)數(shù)字，當(dāng)掃描到下標(biāo)為i的數(shù)字時(shí)，首先比較這個(gè)數(shù)字(m)是不是等于i；如果是，則接著掃描下一個(gè)數(shù)字；如果不是，則再拿它和第m個(gè)數(shù)字進(jìn)行比較，如果它和第m個(gè)數(shù)字相等，就找到了一個(gè)重復(fù)的數(shù)字，如果它和第m個(gè)數(shù)字不相等，就把第i個(gè)數(shù)字和第m個(gè)數(shù)字交換，把m放到屬于它的位置。接下來(lái)重復(fù)這個(gè)比較、交換的過(guò)程，直到發(fā)現(xiàn)一個(gè)重復(fù)的數(shù)字。

bool duplicate(int numbers[], int length, int* duplication){if(numbers == nullptr || length < 0)return false;for(int i=0; i < length; i++){if(numbers[i]<0 || numbers[i]>length-1)return false;}for(int i=0; i < length; i++){while(numbers[i] != i){if(numbers[i] == numbers[numbers[i]]){*duplication = numbers[i];return true;}int temp = numbers[i];numbers[i] = numbers[temp];numbers[temp] = temp;}}return false; }

二、問(wèn)題描述: 不修改數(shù)組找出重復(fù)的數(shù)字
在一個(gè)長(zhǎng)度為n+1的數(shù)組里的所有數(shù)字都在1-n的范圍內(nèi)，所以數(shù)組中至少有一個(gè)數(shù)字是重復(fù)的。請(qǐng)找出數(shù)組里任意一個(gè)重復(fù)的數(shù)字，但不能修改數(shù)組

• 創(chuàng)建一個(gè)長(zhǎng)度為n+1的輔助數(shù)組，然后逐一把原數(shù)組的每一個(gè)數(shù)字復(fù)制到輔助數(shù)組。如果原數(shù)組中被復(fù)制的數(shù)字是m，則把它復(fù)制到輔助數(shù)組中下標(biāo)為m的位置，這樣就很容易發(fā)現(xiàn)哪個(gè)數(shù)字是重復(fù)的。該方案需要O(n)的輔助空間
• 某范圍里數(shù)字的個(gè)數(shù)。把1-n的數(shù)字從中間的數(shù)字m分為兩部分，前面一半為1-m，后面一半為m+1-n。如果1-m的數(shù)字的個(gè)數(shù)超過(guò)m，那么這一半的區(qū)間里一定包含重復(fù)的數(shù)字；否則，另一半m+1-n的區(qū)間里一定包含重復(fù)的數(shù)字。繼續(xù)把包含重復(fù)數(shù)字的區(qū)間一分為二，直到找到一個(gè)重復(fù)的數(shù)字。和二分查找算法很類(lèi)似，只是多了一步統(tǒng)計(jì)區(qū)間里數(shù)字的數(shù)目。

int countRange(const int* numbers, int length, int start, int end){if(numbers == nullptr)return 0;int count = 0;for(int i=0; i < length; i++){if(numbers[i]>=start && numbers[i]<=end){++count;}}return count; }int getDuplication(const int* numbers, int length){if(numbers==nullptr || length<=0)return -1;int start = 1;int end = length-1;while(end >= start){int middle = (end-start)>>2 + 1;int count = countRange(numbers, length, start, middle);if(end == start){if(count > 1)return start;elsebreak;}if(count > (middle-start+1))end = middle;elsestart = middle+1;}return -1; }按照二分查找的思路，如果輸入長(zhǎng)度為n的數(shù)組，那么函數(shù)countRange()將被調(diào)用O(logn)次，每次需要O(n)的時(shí)間，因此總的時(shí)間復(fù)雜度是O(nlogn),空間復(fù)雜度為O(1). posted on 2018-06-16 10:05 Coding_ML 閱讀(...) 評(píng)論(...) 編輯 收藏

轉(zhuǎn)載于:https://www.cnblogs.com/CodingML-1122/p/9189911.html

總結(jié)

以上是生活随笔為你收集整理的2-数组中重复的数字的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。