25 Find the Duplicate Number

[zwkcoding]

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

if not ,the use sort first ,then linear search with O(n) You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). Force search is refused There is only one duplicate number in the array, but it could be repeated more than once.

Two solutions:

• binary search with O(NlogN )time and O(1) space

  class Solution(object):
  def findDuplicate(self, nums):
      low = 1
      high = len(nums) - 1
      while low < high:
          mid = low + (high - low) / 2
          count  = 0
          for i in nums:
              if i <= mid:
                  count += 1
              if count <= mid:
                  low = mid + 1
              else:
                  high = mid
      return low

  idea: I was thinking Binary Search is supposed to be used on sorted array, but this solution impressed me. Find and count can also be a fantastic way to apply the idea of Binary Search.

• floyd circle algorithm with Linked List Cycle

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

  idea: how to think the array as linked list ? see here:http://yucoding.blogspot.com/2017/01/leetcode-question-find-duplicate-number.html