forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
find-the-duplicate-number.py
85 lines (79 loc) · 2.35 KB
/
find-the-duplicate-number.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# Time: O(n)
# Space: O(1)
#
# Given an array nums containing n + 1 integers where each integer
# is between 1 and n (inclusive), prove that at least one duplicate
# element 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 extra space.
# - Your runtime complexity should be less than O(n^2).
#
# Two pointers method, same as Linked List Cycle II.
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# Treat each (key, value) pair of the array as the (pointer, next) node of the linked list,
# thus the duplicated number will be the begin of the cycle in the linked list.
# Besides, there is always a cycle in the linked list which
# starts from the first element of the array.
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
# Time: O(nlogn)
# Space: O(1)
# Binary search method.
class Solution2(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left, right = 1, len(nums) - 1
while left <= right:
mid = left + (right - left) / 2
# Get count of num <= mid.
count = 0
for num in nums:
if num <= mid:
count += 1
if count > mid:
right = mid - 1
else:
left = mid + 1
return left
# Time: O(n)
# Space: O(n)
class Solution3(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
duplicate = 0
# Mark the value as visited by negative.
for num in nums:
if nums[abs(num) - 1] > 0:
nums[abs(num) - 1] *= -1
else:
duplicate = abs(num)
break
# Rollback the value.
for num in nums:
if nums[abs(num) - 1] < 0:
nums[abs(num) - 1] *= -1
else:
break
return duplicate