LeetCode----Find the Duplicate Number

LeetCode----Find the Duplicate Number

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:

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(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.
   

   分析：

   給定一個數組，數組長度為n＋1，裡面的數都在1和n之間，這樣，數組裡肯定有一個數是出現兩次的。假定只有一個數字重復了，找出那個重復數。

   要求：數組不可修改，只讀；只能使用常數個空間；算法復雜度要小於O（n^2），即不能暴力；假定那個重復數只有一個，但是可以出現許多次。

   這題想了好久沒想出來。查看了Discuss才明白。

   第一種解法：

   使用弗洛伊德循環檢測法，記得昨天才寫了一題叫Linked List Cycle，這題就是用該檢測法寫出來的。

   思路是，根據數組元素的特點，將數組元素與下標一一映射起來。比如數組是13422，則0對應1，1對應3，2對應4等。這樣，如果將這種映射當成鏈的話，可以順著下標，下標對應的值，下標對應值的對應下標的值，一直遍歷，鏈中有環，則最後一定會進行循環中，比如對於上面的數組，最後陷入了循環下標2對應值4，下標4對應值2，下標2對應值4，如此循環。

   單單找到了循環還不夠，我們還需要找到進入循環的那個數字，它才是要找的重復數。可以重新用一個下標為0的值從頭開始映射，這樣與前面循環中的指針相遇時，找到的就是循環的起點。

    

   代碼1：

    

   class Solution(object):
       def findDuplicate(self, nums):
           
           :type nums: List[int]
           :rtype: int
           
           slow, fast = 0, 0
           while True:
               slow = nums[slow]
               fast = nums[nums[fast]]
               if slow == fast:
                   break
           # fast和slow一定在循環中某點相遇了，但是相遇的點不一定是剛剛進入循環的那個元素，
           # 需要從0開始繼續尋找
           find = 0
           while find != slow:
               slow = nums[slow]
               find = nums[find]
           return find

   
   
   

    

   第二種解法：

   使用二分法。

    

   代碼：

    

   class Solution(object):
       def findDuplicate(self, nums):
           
           :type nums: List[int]
           :rtype: int
           
           l, r = 0, len(nums) - 1
           while l <= r:
               mid = l + (r - l) / 2
               cnt = 0
               for n in nums:
                   if n <= mid:
                       cnt += 1
               if cnt > mid:
                   r = mid - 1
               else:
                   l = mid + 1
           return l