Missing Ranges
Total Accepted: 9886 Total Submissions: 33922 Difficulty: Medium
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"].
思路
- 硬做
- 先判断lower -> nums[0]
- 再判断nums数组里边的
- 再判断nums[size - 1] -> upper
- 同时要注意,如果数组为空,并不是返回为空
- 这个时候返回的是lower -> upper(如果lower和upper一样,就返回一个字符)
- 虽然很简单,但是太容易犯错了
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new ArrayList<String>();
if (nums == null) {
return result;
}
if (nums.length == 0) {
StringBuilder sb = new StringBuilder();
if (lower == upper) {
sb.append(lower);
} else {
sb.append(lower);
sb.append("->");
sb.append(upper);
}
result.add(sb.toString());
return result;
}
int size = nums.length;
if (lower < nums[0]) {
StringBuilder sb = new StringBuilder();
if (lower < nums[0] - 1) {
sb.append(lower);
sb.append("->");
sb.append(nums[0] - 1);
} else {
sb.append(lower);
}
result.add(sb.toString());
}
for (int i = 1; i < size; i++) {
if (nums[i] - nums[i - 1] != 1) {
StringBuilder sb = new StringBuilder();
if (nums[i] - nums[i - 1] == 2) {
sb.append(nums[i - 1] + 1);
} else {
sb.append(nums[i - 1] + 1);
sb.append("->");
sb.append(nums[i] - 1);
}
result.add(sb.toString());
}
}
if (nums[size - 1] < upper) {
StringBuilder sb = new StringBuilder();
if (nums[size - 1] < upper - 1) {
sb.append(nums[size - 1] + 1);
sb.append("->");
sb.append(upper);
} else {
sb.append(upper);
}
result.add(sb.toString());
}
return result;
}
}
更简洁的写法
- 首先是函数复用
- 其次这个把lower当做了数组第一个数,upper当做了最后一个数
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new ArrayList<>();
for (int i = 0; i <= nums.length; i++) {
int start = i == 0 ? lower : nums[i - 1] + 1;
int end = i == nums.length ? upper : nums[i] - 1;
addMissing(result, start, end);
}
return result;
}
public void addMissing(List<String> result, int start, int end) {
if (start > end) return;
else if (start == end) result.add(start + "");
else result.add(start + "->" + end);
}
}