2021-02-14 287. 寻找重复数

题目地址

https://leetcode-cn.com/problems/find-the-duplicate-number/

题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3：
输入：nums = [1,1]
输出：1
示例 4：
输入：nums = [1,1,2]
输出：1
 
提示：
2 <= n <= 3 * 104
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
 
进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以在不修改数组 nums 的情况下解决这个问题吗？
你可以只用常量级 O(1) 的额外空间解决这个问题吗？
你可以设计一个时间复杂度小于 O(n2) 的解决方案吗？

思路

1. 包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），如果arr[i] != i+1我们不断交换，如果没有重复值，肯定所有的位置arr[i]一定等于i+1，因为一定有重复的，所以一定会arr[i] != arr[arr[i] - 1]，我们返回arr[i]即可。
2. 快慢指针也可以。和链表寻找环入口那题类似，快慢步伐相遇之后，fast再从0开始和slow相同步伐走，当再次相等时就是环入口。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/14 10:42 下午
 */
public class FindDuplicate {
    public static void main(String[] args) {
        int[] arr = {1,3,4,1,2};
        int result = findDuplicateV2(arr);
        System.out.println(result);

        result = findDuplicate(arr);
        System.out.println(result);

    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.2 MB, 在所有 Java 提交中击败了92.70%的用户
     */
    private static int findDuplicateV2(int[] arr) {
        int slow = arr[0];
        int fast = arr[arr[0]];
        while (true) {
            slow = arr[slow];
            fast = arr[arr[fast]];
            if (fast == slow) {
                fast = 0;
                while (arr[slow] != arr[fast]) {
                    slow = arr[slow];
                    fast = arr[fast];
                }
                return arr[slow];
            }
        }
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了73.55%的用户
     * 内存消耗：38.4 MB, 在所有 Java 提交中击败了68.59%的用户
     */
    private static int findDuplicate(int[] arr) {
        for (int i=0; i<arr.length; i++) {
            while (arr[i] != i+1) {
                if (arr[i] != arr[arr[i] - 1]) {
                    swap(arr, i, arr[i] - 1);
                } else {
                    return arr[i];
                }
            }
        }
        return -1;
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}