Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given
Solution 1: iterate the array, O(n) solution below:[0, 1, 3, 50, 75]
, lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
int n=nums.length;
List<String> res=new ArrayList<>();
for (int i=0; i<n; i++) {
if (nums[i]<lower) continue;
else if (nums[i]==lower) lower++;
else {
int hi=Math.min(nums[i]-1,upper);
if (lower==hi) res.add(String.valueOf(lower));
else if (lower<hi) res.add(String.valueOf(lower)+"->"+String.valueOf(hi));
lower=nums[i]+1;
}
if (lower>upper) break;
}
if (lower==upper) res.add(String.valueOf(lower));
else if (lower<upper) res.add(String.valueOf(lower)+"->"+String.valueOf(upper));
return res;
}
}
没有评论:
发表评论