Find the Duplicate Number

原題鏈接Find the Duplicate Number

給定一定大小為n+1的數組，數組中的元素只可能是1到n中的數字，包括1和n。在數組中，有一個數字重復了多次，找到這個數字。
要求不能改變源數組的值，空間復雜度為O(1)，時間復雜度要小于O(n2)。

注意數組中每個元素都只能是1到n之間的數字，這提供了一個有用的信息，即

• 對于每個元素，可以用它的大小和[1: n]之間的數字比較

什么意思呢，假設數組中只有n個元素，而每個元素的大小都在[1 : n]之間，且沒有重復元素。那么對于1到n中的某個值w而言，整個數組中小于等于w的元素個數恰好等于w。可以通過先將數組排序后證明

接著，n個元素的時候恰好[1 : n]各一個，現在，隨機從[1 : n]中選擇一個數字添加到數組中，使數組元素個數變為n+1。此時，對于某個值w而言。如果添加的數字小于等于w，那么小于等于w的元素個數將大于w（因為添加前是等于w）。反之，如果添加的數字大于w，那么小于等于w的元素個數將小于w。

現在，假設數組元素個數為n+1，因為數組元素只有n中取值，所以數組中會有重復元素，可能重復多次。那么此時對于1到n+1中的某個值w而言，整個數組中小于等于w的元素個數就會有三種可能

• 數組中小于等于w的元素個數恰好等于w。這可以說明在數組所有元素中，值在[1 : w]這個范圍內的元素沒有重復，重復元素在[w + 1 : n]中。

  • 證明，反證法。如果有重復元素，那么[w + 1 : n]這個范圍內的元素將不會重復，那么數組中元素總個數為w + (n - w - 1 + 1) = n。而實際上數組元素個數為n+1，矛盾。

• 數組中小于等于w的元素個數小于w。這可以說明在數組所有元素中，值在[1 : w]這個范圍內的元素沒有重復，重復元素在[w + 1 : n]中。

  • 證明，反證法。因為小于等于w的元素個數小于w，所以大于w的元素個數大于n + 1 - w。如果[w + 1 : n]沒有重復元素，那么大于w的元素個數最多為n - w，矛盾。

• 數組中小于等于w的元素個數大于w。這可以說明在數組的所有元素中，重復元素在[1 : w]中。

  • 證明，反證法。如果[1 : w]范圍內沒有重復的元素，那么小于等于w的元素個數最多為w，不可能大于w，矛盾。

---

通過這種劃分，讓上述w取當前區間的中值，就可以采用二分法找到重復的那個元素，代碼如下

class Solution { public:int findDuplicate(vector<int>& nums) {int left = 1;int right = nums.size();while(left < right){/* 取區間的中值作為w */int middle = left + (right - left) / 2;int count = 0;/* 計算數組中所有小于等于w的元素個數 */for(auto n : nums){if(n <= middle)++count;}/* 如果個數小于等于w，說明重復元素在[w+1 : n]的范圍內 */if(count <= middle)left = middle + 1;elseright = middle;}return left;} };

---

其實仔細想一下，時間復雜度小于O(n2)的無非O(1)，O(lgn)，O(n)，O(nlgn)幾種，又要求空間復雜度是O(1)，那么O(n)之前的幾乎都沒戲了，所以只可能是O(nlgn)。又因為O(lgn)通常和二分法聯系在一起，所以很明顯需要使用二分法。又因為數組元素在[1 : n]之間，所以可以用數組大小和下標作比較，即通過比較然后利用二分縮小范圍。

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----给定大小为n+1的数组，元素大小在[1 : n]之间，只有一个元素会重复出现多次，找到重复的那个的全部內容，希望文章能夠幫你解決所遇到的問題。

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