LeetCode百题【寻找重复数】

题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

1 2	`输入：nums = [1,3,4,2,2] 输出：2`

示例 2：

1 2	`输入：nums = [3,1,3,4,2] 输出：3`

提示：

1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现一次

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

解法

排序

class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        int res=nums[0];
        int length=nums.length;
        for (int i = 1; i < length; i++) {
            if (nums[i-1]==nums[i]){
                res=nums[i];
                return res;
            }
        }
        return res;
    }
}

时间复杂度：O(nlogn)

哈希表

class Solution {
    public int findDuplicate(int[] nums) {
        int res=nums[0];
        HashSet<Integer> set=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])){
                set.add(nums[i]);
            }
            else {
                res=nums[i];
                return res;
            }
        }
        return res;
    }
}

时间复杂度：O(n)

快慢指针
- 根据题目，数字范围都在1 -n之间，可建立下标与值的映射关系，因此可以类比环状链表
- 由于存在重复的数字target，因此target 这个位置一定有起码两条指向它的边
- 快慢指针从同一地点出发，快指针每次移动2个单位，慢指针每次移动1个单位，如果存在环，则两者相遇
- 在相遇位置，快指针比慢指针多走了若干圈
- 2(a+b)=a+b+kL（2表示快指针只比慢指针多走一圈，也就是第一次相遇）
  - a：从起点到环起点的长度
  - b：从环起点到相遇点的长度
  - c：从相遇点到环起点的长度
  - L:一圈的长度
- a=(k−1)L+(L−b)=(k−1)L+c
- 也就是说，此时让慢指针从起点出发走，慢指针从相遇位置继续走，两者相遇时必定为环的起点

class Solution {
    public int findDuplicate(int[] nums) {
        int slow=0;
        int fast=0;
        do {
            slow=nums[slow];
            fast=nums[nums[fast]];
        }while (slow!=fast);
        //此时两者相遇，将慢指针放置到起点
        slow=0;
        while (slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
}