287. finding duplicates

• violence ： Two layers of for loop

Speed pointer

class Solution {
    
    public int findDuplicate(int[] nums) {
    
        int slow = 0;
        int fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        // fast  Move back two steps ,slow  Move a step , Find the meeting node 
        // This movement doesn't understand what's going on 
        while(slow != fast){
    // namely 
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        // Find the entry node 
        int pre1 = 0;
        int pre2 = slow;
        while(pre1 != pre2){
    
            pre1 = nums[pre1];
            pre2 = nums[pre2];
        }
        return pre1;
    }
}

Two points search

class Solution {
    
    public int findDuplicate(int[] nums) {
    
        int n = nums.length;
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
    
        	// Keep cutting the array , change mid Value 
            int mid = (l + r) >> 1;
            int cnt = 0;
            // Less than... In the statistics array mid The number of 
            for (int i = 0; i < n; ++i) {
    
                if (nums[i] <= mid) {
    
                    cnt++;
                }
            }
            // Quantity ratio mid Small , So the front ones are all in line with , So change left Value 
            if (cnt <= mid) {
    
                l = mid + 1;
            // Quantity ratio mid many , Change right right Value , By the way, the current mid Assign to ans
            } else {
    
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
}