Missing Ranges
Problem:
Analysis:
It is hard to check the boundaries, so add lower - 1 and upper + 1 to the nums array. However, adding or subtracting would cause overflow issue. It is too much to consider over flow for this problem. So use long instead of int to avoid overflow.
Solution:
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"].
It is hard to check the boundaries, so add lower - 1 and upper + 1 to the nums array. However, adding or subtracting would cause overflow issue. It is too much to consider over flow for this problem. So use long instead of int to avoid overflow.
Solution:
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new LinkedList<>();
long prev = (long)lower - 1;
for (int i = 0; i <= nums.length; i++) {
long cur = (i == nums.length) ? ((long)upper + 1) : (long)nums[i];
if (cur - prev >= 2) {
result.add(getRange(prev + 1, cur - 1 ));
}
prev = cur;
}
return result;
}
private String getRange(long from, long to) {
return (from == to) ? String.valueOf(from) : from + "->" + to;
}
}
评论
发表评论