【Check 87】2024-05-31 - 287. 寻找重复数

[larscheng]

287. 寻找重复数

[larscheng]

思路

n+1个数字放在数组中，n+1个数字的范围都在【1,n】中，所以必定至少有一个重复数字 通过2分法来找这个重复数字，需要一个2分条件，并且应该对值域进行2分，而不是下标索引2分

值域2分，mid = （1+n）/2 在原数组中小于等于mid的数字个数为count

• 如果count>mid,则原数组中取值在【1，mid】的数个数超过了mid，说明有重复，所以重复数字在左边
• 如果count<=mid，则重复数组在右边

代码

    public int findDuplicate(int[] nums) {
        int left = 1;
        //给n+1个数字的数字，其值域在1-n，所以n=len-1
        int right = nums.length - 1;
        while (left<right){
            int mid = (left+right)/2;
            int count =0;
            //数组中小于等于mid的元素个数
            for (int num : nums) {
                if (num<=mid){
                    count++;
                }
            }
            //一个萝卜一个坑，萝卜多了，肯定是挤在了一个坑（有重复）
            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

复杂度

• 时间复杂度：O(n*logn)
• 空间复杂度：O(1)

[larscheng]

思路

• 参考142环形链表2思路 #12 数组必有1个重复数字，转换成链表表示，该链表存在环
• 下标0->nums[0] f(0)=nums[0]=1
• 下标1->nums[1] f(1)=nums[1]=3
• ....
• f(nums[0])->f(1)=3

• 如果有重复，此时就会存在环

  求重复数字 相当于求环入口元素 可以通过快慢指针求解

O(n)/O(1)

代码

   public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        //慢指针每次1步，快指针每次2步
        slow = nums[slow];
        fast = nums[nums[fast]];
        while (slow!=fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return fast;
    }