LeetCode 287的二分法。谁帮我看看。快疯了

代码如下。第25，26两行，大家能看明白吗?  

代码可以运行～  

求一粒米～～（送米的保证回送）

1. class Solution {
   
2.    
   
3.         public int findDuplicate(int[] nums) {  
   
4.             
   
5.             int lo = 1; //  注意，这里不是序号，而是数字本身
   
6.             int hi = nums.length - 1;  
   
7.             
   
8.             int mid = 0;
   
9.             int cnt = 0;
   
10.             
    
11.             while (lo + 1 < hi) {      
    
12.                
    
13.                                     mid = lo + (hi - lo)/2;
    
14.                  
    
15.                                         for (int a : nums)  if (a <= mid)  ++cnt;        
    
16.                                           
    
17.                                         if (cnt > mid) hi = mid;  // cnt多过本来应该有的数目  
    
18.                                         else lo = mid;   
    
19.                
    
20.                     cnt = 0;
    
21.                         }   
    
22. 
    
23.                    for (int a : nums)  if (a == lo)  ++cnt;   
    
24.                   
    
25.                    if(cnt > 1) return lo;
    
26.                    else return hi;
    
27.             
    
28.         }
    
29. }
    

复制代码

shuatigq 发表于 2020-9-28 22:20
这题不是双指针吗？没排序也能二分？

这道题和平时的二分不太一样。。

是用二分的方式估计一个数n， 然后看小于等于n的个数是否为n

如果大于n，那么说明duplicate的那个数字小于等于n

反之duplicate的数字大于n

shuatigq 发表于 2020-9-28 22:20
这题不是双指针吗？没排序也能二分？

双指针也是能做的。

主要看这三行。。跳出循环后,high = lo + 1;
所以就剩下两个数，
然后统计了以下low的个数是否为2.。如果是2的话，返回low，不然的话就是high有两个

for (int a : nums)  if (a == lo)  ++cnt;   
            
if(cnt > 1) return lo;
else return hi;

这个模版是为了避免二分法容易出现的死循环，所以在hi= lo + 1的时候就退出while循环，这个时候其实low 和 high 是相邻挨着， 所以你要分别对low 和 high在做一次判断，如果low算出来的count  > count, 就return left 因为left 肯定是那个duplicate number, 如果不是 那就return right.  

补充内容 (2020-9-29 22:19):
这里low high和 left right 是一个意思，打错了. 然后 count > count应该是count > left

因为最后Low比high少1就跳出循环了,所以需要再判断一下到底是low还是high是重复数.

另一种方法是让low=high的时候跳出循环,这样不需要再额外判断一次.但是需要注意循环内部low和high的赋值,以免死循环