// 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"].
import java.util.*;
public class MissingRanges {
public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
ArrayList<String> result = new ArrayList<String>();
for(int i = 0; i <= nums.length; i++) {
long start = i == 0 ? lower : (long)nums[i - 1] + 1;
long end = i == nums.length ? upper : (long)nums[i] - 1;
addMissing(result, start, end);
}
return result;
}
static void addMissing(ArrayList<String> result, long start, long end) {
System.out.println("adding range:"+start+"..."+end);
if(start > end) {
return;
} else if(start == end) {
result.add(start + "");
} else {
result.add(start + "->" + end);
}
}
public static List<String> findMissingRanges2(int[] nums, int lower, int upper) {
int ind = 0;
ArrayList<String> result = new ArrayList<String>();
for(int i=lower; i<=upper; i++){
if(ind<nums.length && nums[ind]>i){
addMissing(result, i, nums[ind]-1);
i = nums[ind];//move i till it reaches nums[mid] because i to nums[mid]-1 is already added
}else if(ind>=nums.length && i<upper){
addMissing(result, i, upper);
i=upper;//no more ranges to be added, the array is exhausted
}
ind++;
}
return result;
}
public static void main(String[] args){
int[] nums = {10, 11, 13, 50, 75};
List<String> res1 = findMissingRanges(nums, 0, 99);
List<String> res2 = findMissingRanges2(nums, 0, 99);
System.out.println(Arrays.toString(res1.toArray()));
System.out.println(Arrays.toString(res2.toArray()));
}
}
// For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
import java.util.*;
public class MissingRanges {
public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
ArrayList<String> result = new ArrayList<String>();
for(int i = 0; i <= nums.length; i++) {
long start = i == 0 ? lower : (long)nums[i - 1] + 1;
long end = i == nums.length ? upper : (long)nums[i] - 1;
addMissing(result, start, end);
}
return result;
}
static void addMissing(ArrayList<String> result, long start, long end) {
System.out.println("adding range:"+start+"..."+end);
if(start > end) {
return;
} else if(start == end) {
result.add(start + "");
} else {
result.add(start + "->" + end);
}
}
public static List<String> findMissingRanges2(int[] nums, int lower, int upper) {
int ind = 0;
ArrayList<String> result = new ArrayList<String>();
for(int i=lower; i<=upper; i++){
if(ind<nums.length && nums[ind]>i){
addMissing(result, i, nums[ind]-1);
i = nums[ind];//move i till it reaches nums[mid] because i to nums[mid]-1 is already added
}else if(ind>=nums.length && i<upper){
addMissing(result, i, upper);
i=upper;//no more ranges to be added, the array is exhausted
}
ind++;
}
return result;
}
public static void main(String[] args){
int[] nums = {10, 11, 13, 50, 75};
List<String> res1 = findMissingRanges(nums, 0, 99);
List<String> res2 = findMissingRanges2(nums, 0, 99);
System.out.println(Arrays.toString(res1.toArray()));
System.out.println(Arrays.toString(res2.toArray()));
}
}
No comments:
Post a Comment