【leetcode】287. Find duplicates

subject ：

287.  Look for repetitions 
 Given an inclusion  n + 1  Array of integers  nums , The numbers are all in  [1, n]  Within the scope of （ Include  1  and  n）, We know that there is at least one duplicate integer .
 hypothesis  nums  Only   A repeated integer  , return   The number of repetitions  .
 The solution you design must   Don't modify   Array  nums  And only constant level  O(1)  Extra space .

 Example  1：

 Input ：nums = [1,3,4,2,2]
 Output ：2
 Example  2：

 Input ：nums = [3,1,3,4,2]
 Output ：3

 Tips ：

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums  in   There's only one whole number   appear   Two or more times  , Other integers only appear   once 

Dichotomy ：
It can be analyzed in combination with drawer principle .

class Solution {
    
    public int findDuplicate(int[] nums) {
    
        //  Use dichotomy 
         /* Less than O(n^2)  Two points search   Let's not think about arrays , Just think about it   The numbers are all there  1  To  n  Between   Example  1: arr = [1,3,4,2,2]  At this time, the number is in  1 — 5  Between  mid = (1 + 5) / 2 = 3 arr Less than or equal to 3 Yes 4 individual (1,2,2,3),1 To 3 There must be duplicate values in  mid = (1 + 3) / 2 = 2 arr Less than or equal to 2 Yes 3 individual (1,2,2),1 To 2 There must be duplicate values in  mid = (1 + 2) / 2 = 1 arr Less than or equal to 1 Yes 1 individual (1),2 To 2 There must be duplicate values in   So the number of repetitions is  2 */
        int low = 0, high = nums.length - 1, mid = -1, count;
        while ( low < high ) {
    
            //  Guess the middle point is repeated , Find the number less than or equal to the middle number , If it is equal to the middle number, it means there is no repetition , Move up the interval , Otherwise, the interval has repetition number 
            mid = (low + high) / 2;
            count = 0;
            for (int num : nums) {
    
                if(num <= mid) {
    
                    count ++;
                }
            }
            //  If the number of values of the number is less than or equal to the number , Then slide up the interval 
            if ( count <= mid ) {
    
                low = mid + 1;
            } else {
    
                //  The number of occurrences is greater than this value , Then down 
                high = mid;
            }
        }
        return low;
    }
}