163. Missing Ranges

发表于 | 分类于

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 and upper = 99, return [“2”, “4->49”, “51->74”, “76->99”].

解法1：

挺无聊的一道题，主要是corner case比较多。
算法不难，就是遍历一遍数组。找出是否是连续的数，如果不是那么补上缺少的range。
corner case有：
缺少的是一个数，不是range
两个相同的数
数字已经是Integer.MAX_VALUE，会溢出。
C++

1

Java

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
public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<String>();
        if (nums.length == 0) {
            if (lower == upper) {
                res.add(Integer.toString(lower));
            } else {
                res.add(Integer.toString(lower) + "->" + Integer.toString(upper));
            }
            return res;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (i == 0 && nums[i] > lower) {
                if (nums[i] == lower + 1) {
                    res.add(Integer.toString(lower));
                } else {
                     res.add(Integer.toString(lower) + "->" + Integer.toString(nums[i] - 1));
                }
            } else if (i != 0) {
                if (nums[i] != nums[i - 1] && nums[i] > nums[i - 1] + 1) {
                    if (nums[i] == nums[i - 1] + 2) {
                        res.add(Integer.toString(nums[i - 1] + 1));
                    } else {
                        res.add(Integer.toString(nums[i - 1] + 1) + "->" + Integer.toString(nums[i] - 1));
                    }
                }
            }
            if (i == nums.length - 1) {
                if (upper > nums[i]) {
                    if (upper == nums[i] + 1) {
                        res.add(Integer.toString(upper));
                    } else {
                        res.add(Integer.toString(nums[i] + 1) + "->" + Integer.toString(upper));
                    }
                }
            }
        }
        return res;
    }
}