forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
missing-ranges.py
40 lines (33 loc) · 1.08 KB
/
missing-ranges.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
# Time: O(n)
# Space: O(1)
#
# Given a sorted integer array where the range of elements are [lower, upper] inclusive,
# return its missing ranges.
#
# For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99,
# return ["2", "4->49", "51->74", "76->99"].
#
class Solution:
# @param A, a list of integers
# @param lower, an integer
# @param upper, an integer
# @return a list of strings
def findMissingRanges(self, A, lower, upper):
ranges = []
pre = lower - 1
for i in xrange(len(A) + 1):
if i == len(A):
cur = upper + 1
else:
cur = A[i]
if cur - pre >= 2:
ranges.append(self.getRange(pre + 1, cur - 1))
pre = cur
return ranges
def getRange(self, lower, upper):
if lower == upper:
return "{}".format(lower)
else:
return "{}->{}".format(lower, upper)
if __name__ == "__main__":
print Solution().findMissingRanges([0, 1, 3, 50, 75], 0, 99)