633. 寻找重复的数

描述

给出一个数组 nums 包含 n + 1 个整数，每个整数是从 1 到 n (包括边界)，保证至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

注意事项

1.不能修改数组(假设数组只能读)
2.只能用额外的O(1)的空间
3.时间复杂度小于O(n^2)
4.数组中只有一个重复的数，但可能重复超过一次

样例

给出 nums = [5,5,4,3,2,1]，返回 5.
给出 nums = [5,4,4,3,2,1]，返回 4.

思路

如果每个数只出现一次，那必然会有对于当前数 x，数组中小于 x 的数出现的总次数小于等于 x，所以一旦出现重复数就会使得对于当前数 y，数组中小于 y 的数出现的总次数大于 y，即构成了二分条件

代码

1. 二分法
   nlogn

public class Solution {
    /**
     * @param nums an array containing n + 1 integers which is between 1 and n
     * @return the duplicate one
     */
    public int findDuplicate(int[] nums) {
        int start = 1;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (check_smaller_num(mid, nums) <= mid) {
                start = mid;
            } else {
                end = mid;
            }
        }
            
        if (check_smaller_num(start, nums) <= start) {
            return end;
        }
        return start;
    }
    
    public int check_smaller_num(int mid, int[] nums) {
        int cnt = 0;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] <= mid){
                cnt++;
            }
        }
        return cnt;
    }
}

2. 映射法

public class Solution {
    /**
     * @param nums an array containing n + 1 integers which is between 1 and n
     * @return the duplicate one
     */
    public int findDuplicate(int[] nums) {
        // Write your code here
        if (nums.length <= 1)
            return -1;

        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
}