查找数组中的重复 - 时间复杂度<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; 
}