查找數組中的重複 - 時間複雜度<O（n^2）和常量額外空間O（1）。 （亞馬遜訪談）

Question

下面給出的是問題陳述和解決方案。我無法理解解決方案背後的邏輯。

問題陳述：
鑑於包含n + 1點的整數，其中每個整數是1和n（含）之間的陣列NUMS，證明至少有一個重複的數目必須存在。假設只有一個重複號碼，找到重複號碼。

注意： 您不得修改數組（假定數組是隻讀的）。 您只能使用恆定的O（1）額外空間。 您的運行時複雜度應該小於O（n2）。 數組中只有一個重複數字，但可以重複多次。

採樣輸入：[3 4 1 4 1] 輸出：用於貼在本文給出了問題1個

的解是：

class Solution(object): 
    def findDuplicate(self, nums): 
     """ 
     :type nums: List[int] 
     :rtype: int 
     """ 
     low = 1 
     high = len(nums)-1 

     while low < high: 
      mid = low+(high-low)/2 
      count = 0 
      for i in nums: 
       if i <= mid: 
        count+=1 
      if count <= mid: 
       low = mid+1 
      else: 
       high = mid 
     return low 

說明用於上述代碼（按作者）： 該解決方案基於二分查找。

首先搜索空間是1到n之間的數字。每次我選擇一個數字（這是中間的數字），並計算所有等於或小於中等數字的數字。然後，如果計數超過中間值，搜索空間將爲[1 mid]，否則爲[mid + 1 n]。我這樣做直到搜索空間只有一個數字。

假設n = 10，我選擇mid = 5。然後我計算數組中所有小於等於中間的數字。如果5個以上的數字小於5，那麼按照鴿王原理（https://en.wikipedia.org/wiki/Pigeonhole_principle），其中一個已經出現過一次以上。所以我縮小了從[110]到[1 5]的搜索空間。否則重複號碼在下半部分，因此下一步搜索空間將會是[6 10]。

的疑問：在上述方案中，當count <= mid，我們爲什麼要改變low到low = mid + 1或以其他方式改變high = mid？ 它背後的邏輯是什麼？

我無法理解這種算法

相關鏈接背後的邏輯： https://discuss.leetcode.com/topic/25580/two-solutions-with-explanation-o-nlog-n-and-o-n-time-o-1-space-without-changing-the-input-array

Answer 1

那麼這是一個二進制搜索。你將搜索空間減半並重復。

想想這樣：你有一個101項的列表，你知道它包含值1-100。以50爲中間點。計算有多少項目小於或等於50.如果有超過50項目小於或等於50，則重複項在0-50範圍內，否則重複項是在51-100範圍內。

二進制搜索只是將範圍減半。看着0-50，取25點並重復。

---

這個算法的關鍵部分我認爲是造成混亂的for循環。我會試着解釋它。首先請注意，在此算法的任何位置都有沒有使用索引 - 只要檢查代碼，就會看到索引引用不存在。其次，請注意，算法循環遍歷整個集合，用於循環的每次迭代。

讓我進行以下更改，然後在每個while循環之後考慮值inspection_count。

inspection_count=0 
for i in nums: 
    inspection_count+=1 
    if i <= mid: 
     count+=1 

當然inspection_count作者將等於len(nums)。 for循環遍歷整個集合，並且對於每個元素來檢查它是否在候選範圍內（值的，而不是索引）。

重複測試本身簡單而優雅 - 正如其他人指出的那樣，這是鴿子的原理。給定n值的集合，其中每個值在{p..q}範圍內，如果q-p < n那麼該範圍內必須有重複值。想一些簡單的情況下 -

p = 0, q = 5, n = 10 
"I have ten values, and every value is between zero and five. 
At least one of these values must be duplicated." 

我們可以概括這一點，但一個更有效和相關的例子是

p = 50, q = 99, n = 50 
"I have a collection of fifty values, and every value is between fifty and ninety-nine. 
There are only forty nine *distinct* values in my collection. 
Therefore there is a duplicate." 

Answer 2

可以說你有10個號碼。

a=[1,2,2,3,4,5,6,7,8,9] 

然後中期= 5 並且是小於或等於5的元素數量是6（1,2,2,3,4,5）。 現在count = 6，這大於mid。這意味着前半部分至少有一個重複，因此代碼所做的工作是將搜索空間設置爲[1-10]到[1-5]的前半部分，依此類推。 否則在下半年發生重複，因此搜索空間將會是[5-10]。

請告訴我，如果你有疑問。

Answer 3

設置low = mid+1或high = mid後面的邏輯本質上是使其成爲基於binary search的解決方案。搜索空間被分成兩半，並且while循環僅在下一個迭代中搜索下半部分（high = mid）或更高半部分（low = mid+1）。

所以我縮小了從[110]到[1 5]的搜索空間。否則重複號碼在下半部分，因此下一步搜索空間將會是[6 10]。

這是關於您的問題的解釋的一部分。

Answer 4

public static void findDuplicateInArrayTest() { 

    int[] arr = {1, 7, 7, 3, 6, 7, 2, 4}; 

    int dup = findDuplicateInArray(arr, 0, arr.length - 1); 

    System.out.println("duplicate: " + dup); 
} 

public static int findDuplicateInArray(int[] arr, int l, int r) { 

    while (l != r) { 

     int m = (l + r)/2; 
     int count = 0; 

     for (int i = 0; i < arr.length; i++) 
      if (arr[i] <= m) 
       count++; 

     if (count > m) 
      r = m; 
     else 
      l = m + 1; 
    } 
    return l; 
}