LC 0287 [M] Find the Duplicate Number - ALawliet/algorithms GitHub Wiki
cyclic sort - modifies the input
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
i = 0
while i < len(nums):
if nums[i] != i + 1:
j = nums[i] - 1
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
return nums[i]
else:
i += 1
return -1
binary search
class Solution(object):
def findDuplicate(self, nums):
lo = 0
hi = len(nums) - 1
mid = (hi + lo) / 2
while hi - lo > 1:
count = 0
for k in nums:
if mid < k <= hi:
count += 1
if count > hi - mid:
lo = mid
else:
hi = mid
mid = (hi + lo) / 2
return hi
fast/slow pointer
def find_duplicate(arr):
slow, fast = arr[0], arr[arr[0]]
while slow != fast:
slow = arr[slow]
fast = arr[arr[fast]]
# find cycle length
current = arr[arr[slow]]
cycleLength = 1
while current != arr[slow]:
current = arr[current]
cycleLength += 1
return find_start(arr, cycleLength)
def find_start(arr, cycleLength):
pointer1, pointer2 = arr[0], arr[0]
# move pointer2 ahead 'cycleLength' steps
while cycleLength > 0:
pointer2 = arr[pointer2]
cycleLength -= 1
# increment both pointers until they meet at the start of the cycle
while pointer1 != pointer2:
pointer1 = arr[pointer1]
pointer2 = arr[pointer2]
return pointer1