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"].
思路:
查看每个数字和上一个数字中是否需要补区间,第一个数字需要和lower做比较,最后一个数字还要和upper做一次比较。
此题坑较多:比如low和up相同,数组为空的case;low和up是int类型的最小和最大值的情况,此时用num[i] - num[i-1]就会有溢出。
public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
String range = "";
if (lower == upper) {
range = String.valueOf(lower);
} else {
range = String.valueOf(lower) + "->" + String.valueOf(upper);
}
//String range = String.valueOf(lower) + "->" + String.valueOf(upper);//bug
res.add(range);
return res;
}
for (int i = 0; i < nums.length; i++) {
String range = "";
//if (i == 0 && nums[i] > lower) {//bug//第一个和lower比
if (i == 0) {//第一个和lower比
if (nums[i] > lower) {
if (nums[i] - 1 == lower) {
range = String.valueOf(lower);
} else {
range = String.valueOf(lower) + "->" + String.valueOf(nums[i] - 1);
}
}
} else {
long diff = (long)nums[i] - (long)nums[i-1];
System.out.println(diff);
if (diff == 2) {//其余的和前一个比
range = String.valueOf(nums[i] - 1);
} else if (diff > 2) {
range = String.valueOf(nums[i-1] + 1) + "->" + String.valueOf(nums[i] - 1);
}
}
if (!range.equals("")) {
res.add(range);
}
//res.add(range);//bug 会向res重复add range
if (i == nums.length - 1 && nums[i] < upper) {//最后一个再和upper比一次
if (upper - 1 == nums[i]) {
range = String.valueOf(upper);
} else {
range = String.valueOf(nums[i] + 1) + "->" + String.valueOf(upper);
}
res.add(range);
}
//res.add(range); //bug 会向res重复add range
}
return res;
}
网友评论