leetcode Find the Duplicate Number

leetcode Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

You must not modify the array (assume the array is read only).

You must use only constant, O(1) extra space.

Your runtime complexity should be less than O(n2).

There is only one duplicate number in the array, but it could be repeated more than once.

题目地址：leetcode Find the Duplicate Number

题意：

给定一个n + 1个数的数组，数组中每个元素的值介于1~n，假设只有一个元素是重复的，求这个元素

你不能修改这个数组
空间复杂度要求O(1)
时间复杂度小于O(n2)
只有一个元素是重复的，但可能重复不止一次

思路：

因为时间复杂度要求要小于O(n2), 所以不能用朴素的判别。

空间复杂度O(1)所以不能hash，不能修改所以不能排序,可能不止重复一次所以不能n项和

所以，怎么做呢？

方法一：二分

我们知道，这总共n + 1 个数每个数x都满足 1 <= x <= n

所以，我们二分答案为 mid = (L+R )/2 其中 L=1 R= n

然后扫描整个数组进行统计，设cnt为满足不大于mid的元素个数，则有：cnt <= mid 则说明重复的应该在 [mid , R] ，否则，应该在[L,mid]

总的时间复杂度为O(nlogn)

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        L, R = 1, len(nums) - 1
        while L <= R:
            mid = (L + R) >> 1
            cnt = sum([1 for num in nums if num <= mid])

            if cnt <= mid:
                L = mid + 1
            else:
                R = mid - 1
        return L

方法二：双指针

如果数组中元素不重复，那么,任意下标i和数组中该下标的值一一对应，如对于数组 3,4,1,2，有如下对应关系：（注意，值从1~n）

0 - > 2
1 -> 4
2 -> 1
3 -> 3

设这个对应关系的运算函数为f(n) ，那么，我们从下标0出发，每次根据f取出下标i对应的值x，并将这个x作为下一次的下标，直到下标越界。

如3，4，1，2这个数组，那么有 0 - > 2-> 1-> 4

但如果有重复的话，中间就会产生多个映射，如3,4,1,2,3

0 - > 2
1 -> 4
2 -> 1
3 -> 3
4 ->3

继续这么做的话，会发生 0 - > 2-> 1-> 4 -> 3 -> 3->3……

也就是最后一定是那个重复的元素。

这样类似于 leetcode 142 Linked List Cycle II一样，找链表环路的起点，我们先用快慢两个下标都从0开始，快下标每轮运算两次，慢下标每轮运算一次，直到两个下标再次相同。这时候保持快下标位置不变，将慢下标移动到0，接着两个每轮分别运算一次，当这两个下标相遇时，就是环的起点，也就是重复的数。

原因详见 142. Linked List Cycle II

时间复杂度为O(n)

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        slow , fast = nums[0] , nums[nums[0]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]

        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow