287. Find the Duplicate Number 「寻找重复数」

2019年11月11日 34点热度 0人点赞 0条评论

给定一个数组 nums,包含 n+1 个整数,每个整数取值范围为 [1, n]。请证明至少存在一个重复的数字。假设数组中只有一个重复的数字,求其值。

例一:
输入: [1,3,4,2,2]
输出: 2

例二:
输入: [3,1,3,4,2]
输出: 3

提示:
1. 禁止修改数组(假设数组只读)。
2. 只能使用 O(1) 的空间。
3. 时间复杂度应小于 O(n2)。
4. 数组中只有一个重复的数字,但是有可能会重复多次。

这个题还是挺有意思的。

第一眼看过去,觉得还挺容易的,我只需要拿个集合存储一下每个数字就好了,每次存之前我都检查一下是否已经包含这个数字就解决了。但是这个题还给了几个限制,不能修改原有数组,不能使用过多的空间,不能太费时,那么比较容易想到的几个方法就都用不了了。

后来看了官方给的解答,才明白这个题的本意。这个题的本质是和之前的 142. Linked List Cycle II 「环形链表 II」是一样的,即找到环形链表中环的第一个节点。但是这个想法的转换不太容易,那我用个表格解释一下。

index / ListNode0123456789
value / next2596938971

这个表格表示了一个 {2,5,9,6,9,3,8,9,7,1} 的数组,上面一行是下标,下面一行是对应的值,在这个题中,我们要把下标的值想象为一个链表节点,把值想象成下一个节点的指针引用。这个数组就可以表示成
0->2->9->1->5->3->6->8->7->9 (开始循环)
之所以可以这么想象,是因为这个题给的条件刚好可以满足。

  1. 在数组中,必然会出现重复的数字,也就是说必然有两个“节点”指向同一个节点,因为我们把值当作指针引用,值相同则指向相同,这样便必然存在环形链表;
  2. 在数组中,所有的值都大于 0,不会有任何“节点”指向它,这样我们就可以把第一个值当作是链表的头节点;
  3. 我们找到的环开始的“节点”可能不是第一个出现重复数字的位置,找到的链表可能不能完全包括所有的重复数字,但这个问题仅要求给出重复数字的值;
  4. 我们找到的链表可能不能完全包括所有的值,但这个问题中重复的数字只有一个。

基于以上的分析,我们便可以放心的去寻找“节点”了,代码和「环形链表 II」完全相同。

/*
 * 287. Find the Duplicate Number
 * https://leetcode.com/problems/find-the-duplicate-number/
 * https://realneo.me/287-find-the-duplicate-number/
 */

public class FindDuplicate {
    public static void main(String[] args) {
        FindDuplicate solution = new FindDuplicate();

        int[] nums = new int[]{1, 3, 4, 2, 2};
        System.out.println(solution.findDuplicate(nums));

        nums = new int[]{3, 1, 3, 4, 2};
        System.out.println(solution.findDuplicate(nums));
    }

    private int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;

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

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

        return head;
    }
}

Neo

与卿再世相逢日,玉树临风一少年。

文章评论