287.Find the Duplicate Number

Tags: [trick], [binary_search], [slow_fast_pointer]

Link: https://leetcode.com/problems/find-the-duplicate-number/#/description

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:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n^2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Solution: Binary Search

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return None

        size = len(nums)
        min_elem = 1
        max_elem = size - 1
        while min_elem < max_elem:
            mid_elem = min_elem + (max_elem - min_elem) / 2
            counter = sum([1 for x in nums if x <= mid_elem])

            # if there is no duplicate, the counter should be equal to mid_elem,
            # but if counter > mid_elem, it means the duplicates should be in the left side.
            if counter > mid_elem:
                max_elem = mid_elem
            else:
                min_elem = mid_elem + 1

        return min_elem

Solution: Binary Search

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            raise ValueError('the input is invalid')

        min_num = 1
        max_num = len(nums) - 1

        while min_num <= max_num:
            mid_num = min_num + (max_num - min_num) / 2
            counter = sum([1 for x in nums if x <= mid_num])

            if counter > mid_num:
                # 如果小于等于中间的数的个数大于中间数，那么在前半部分必有重复
                max_num = mid_num - 1
            else:
                # 否则，后半部分存在重复数
                min_num = mid_num + 1

        return min_num

Revelation:

• 如果小于等于中间数的个数大于中间数，那么在前半部分必有重复，否则后半部分存在重复. If the number of elements which are less than or equal to mid_num is greater than the mid_num, so there must be duplicates in the left part, otherwise the duplicates are in the right part.

Note:

• Time complexity = O(n * lgn), the time complexity of binary search is O(lgn), but in each iteration, we do O(n) linear search. So the total time complexity is O(nlgn). n is the number of elements in the given nums.

Solution: Slow Fast Two Pointers

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            raise ValueError('the input is invalid')

        slow = nums[0]
        fast = nums[nums[0]]

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

        finder = 0
        while finder != slow:
            slow = nums[slow]
            finder = nums[finder]

        return finder

Revelation:

• 如果不存在duplicates，那么数组中的数和其index是一一映射的关系及一个index对应一个element，一个element也只对应一个index，比如，有一个数组 arr = [1, 3, 2], index <-> elem 的映射是: 0<->1, 1<->3, 2<->2, 但是如果存在duplicates的话，index到element的映射就不是一一对应的了，例如，arr = [1, 2, 1], index<->element: 0<->1, 1<->2, 2<->1, 如果我们把他们看成一个链表的话，我们可以从0到1，从1到2，从2到1，这样就出现了回路，也就是环，通过观察我们知道，这个环的起点就是我们要找的duplicate，所以这道题就转化成了我们熟悉的 Linked List Cycle II 找环的起点问题，具体算法的分析请看那道题.

Note:

• Time complexity = O(n), n is the number of elements of the given nums.

Time Limited Exceeded:

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            raise ValueError('the input is invalid')

        for i in xrange(len(nums)):
            for j in xrange(len(nums)):
                if i == j:
                    continue

                if nums[i] == nums[j]:
                    return nums[i]

        return None

Note:

• Time complexity = O(n^2), n is the number of elements of the given nums.