287. 寻找重复数

Posted on 2019-10-16 In Leetcode , Leetcode TOP 100 Views: Disqus:

LeetCode刷题系列。

描述

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

示例 1:

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

示例 2:

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

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 $O(1)$ 的空间。
时间复杂度小于 $O(n^2)$ 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

来源：力扣（LeetCode）
链接：287. Find the Duplicate Number

解题思路

如果没有各种条件的限制，本题应该属于简单题，比如可以利用额外的空间对原数组进行排序，排完序遍历一遍就可以了。然后题目还要求时间复杂度必须小于 $O(n^2)$ ，那么也杜绝了二重循环的暴力法。通常这个时候就考虑一下是不是可以用 $O(nlgn)$ 呢，比如二分法。

本题的一种解法就是二分搜索法，我们首先求出[1,n]区间内的中点mid，然后遍历整个数组，统计所有小于等于mid的数的个数count，这里需要注意，我们要用count与mid相比较来判断重复值的所在区间。如果count小于等于mid，则说明重复值在[mid+n, 1]之间，然后依次类推，就是喜闻乐见的二分搜索套路了。最后剩下的值就是我们要求的重复值。具体代码见解法一。

[LeetCode]Find the Duplicate Number这个链接给出了另外一个更加巧妙的解法，可以在 $O(n)$ 的时间复杂度内得到答案。

该方法的核心思想就是将找重复数的问题转换成一个找环的入口的问题，然后就可以采用Linked List Cycle II中使用过的快慢指针的方法进行求解，环的入口就是需要求解的重复数，因为对数组一圈遍历下来以后，整个环中被遍历过两次的数一定是重复数。

具体分成两步，首先构建环：如果0是指针，指向nums[0]，而nums[0]也是指针，指向nums[nums[0]]，这样我们就可以这样构建数组形成的链表：

int point = 0;
while(true){
    point = nums[point]; // 等同于 next = next->next; 
}

假设有这样一个样例：[1,2,3,4,5,6,7,8,9,5]。如果我们按照上面的循环下去就会得到这样一个路径: 1 2 3 4 5 [6 7 8 9] [6 7 8 9] [6 7 8 9] . . .这样就有了一个环，也就是6 7 8 9。point会一直在环中循环的前进。
这时我们设置两个一快(fast)一慢(slow)两个指针，一个每次走两步，一个每次走一步，这样让他们一直走下去，直到他们在重复的序列中相遇。

int fast = 0, slow = 0;
while(true)
{
    fast = nums[nums[fast]];
    slow = nums[slow];
    if(fast == slow)
        break;
}

相遇以后，再从0开始遍历，直到到达环的入口，返回，具体代码见解法2。

代码

解法一

int findDuplicate(int* nums, int numsSize)
{
    int left = 0, right = numsSize - 1;
    
    while(left < right)
    {
        int mid = left + (right - left) / 2, count = 0;
        for(int i = 0; i < numsSize; i++)
        {
            if(nums[i] <= mid)
            {
                count++;
            }
        }
        
        if(count <= mid)
        {
            left = mid + 1;
        }
        
        else
        {
            right = mid;
        }
    }
    
    return right;
   
}

解法二

int findDuplicate(int* nums, int numsSize)
{
    int fast = 0, slow = 0;
    while(true)
    {
        fast = nums[nums[fast]];
        slow = nums[slow];
        if(fast == slow)
            break;
    }
    
    int finder = 0;
    while(true)
    {
        finder = nums[finder];
        slow = nums[slow];
        if(slow == finder)
            break;        
    }
    
    return slow;

}

描述

解题思路

代码

解法一

解法二

参考