-
Notifications
You must be signed in to change notification settings - Fork 461
Expand file tree
/
Copy path1060_Missing_Element_in_Sorted_Array.py
More file actions
58 lines (49 loc) · 1.79 KB
/
Copy path1060_Missing_Element_in_Sorted_Array.py
File metadata and controls
58 lines (49 loc) · 1.79 KB
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
# Approach 1: one pass through the input array
# Time: O(n) | Space: O(1)
class Solution(object):
def missingElement(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
countOfMissingNumber = 0
for i in range(1, len(nums)):
left = nums[i - 1]
right = nums[i]
if (left + 1) != right:
# Number missing
countOfMissingNumber = right - left - 1
if countOfMissingNumber >= k:
# We have the missing number into this range
return left + k
else:
# Update the missing numbers, because our missing number isn't in this range
k -= countOfMissingNumber
return right + k
# Approach 2: Binary search
# Time: O(nlogn) | Space: O(1)
class Solution(object):
def missingElement(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
actualLength = len(nums)
expectedLength = nums[-1] - nums[0] + 1
missingLength = expectedLength - actualLength
if missingLength < k: # missing number iss beyond the array
return nums[-1] + (k - missingLength)
leftIdx, rightIdx = 0, len(nums) - 1
while leftIdx + 1 < rightIdx:
midIdx = (leftIdx + rightIdx) // 2
currentActualLength = midIdx - leftIdx
currentExpectedLength = nums[midIdx] - nums[leftIdx]
currentMissingLength = currentExpectedLength - currentActualLength
if currentMissingLength < k:
leftIdx = midIdx
k -= currentMissingLength
else:
rightIdx = midIdx
return nums[leftIdx] + k