Google
163 Missing Ranges

1. Question

Given a sorted integer array where the range of elements are in the inclusive range [lower,upper], return its missing ranges.
For example, given[0, 1, 3, 50, 75],lower= 0 andupper= 99, return["2", "4->49", "51->74", "76->99"].

2. Implementation

(1) Scan Line
1
class Solution {
2
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
3
List<String> res = new ArrayList<>();
4
5
for (int i = 0; i <= nums.length; i++) {
6
long start = i == 0 ? lower : (long)nums[i - 1] + 1;
7
long end = i == nums.length ? upper : (long)nums[i] - 1;
8
addMissingRange(res, start, end);
9
}
10
return res;
11
}
12
13
public void addMissingRange(List<String> res, long start, long end) {
14
if (start > end) {
15
return;
16
}
17
18
if (start == end) {
19
res.add(start + "");
20
}
21
else {
22
res.add(start + "->" + end);
23
}
24
}
25
}
Copied!

3. Time & Space Complexity

Scan Line: 时间复杂度O(n), 空间复杂度O(n)