Difficulty: Medium
More:【目录】LeetCode Java实现
Description
Given a sorted integer array where the range of elements are [0, 99] inclusive, return its
missing ranges.
For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]
Example Questions Candidate Might Ask:
Q: What if the given array is empty?
A: Then you should return [“0->99”] as those ranges are missing.
Q: What if the given array contains all elements from the ranges?
A: Return an empty list, which means no range is missing.
Intuition
本题数字范围从[0, 99]拓展为[start,end]
方法一(自己开始时想的)：遍历数组，确定每个缺失区域的开头和结尾。这里需要对数组的第一位和最后一位是否等于start和end单独讨论。
方法二（简单点）：遍历数组，使用cur和pre指针指向当前数字和前一个数字，通过pre和cur的差是否为1可以得到缺失区域的开头和结尾。开始时，pre设置为start-1；结束时，cur设置为end+1，这样可以避免对数组首尾单独进行讨论。
注意：1.数组为空时，应该返回[start->end]；
2.如何返回缺失的数字范围？采用List<String>返回。
Solution
//方法一
public List<String> getMissingRanges(int[] arr,int start,int end){
List<String> list = new ArrayList<String>();
if(arr==null || arr.length<=0) {
list.add(getRange(start, end));
return list;
}
if(arr[0]!=start)
list.add(getRange(start,arr[0]-1));
for(int k=1;k<arr.length;k++) {
if( arr[k]==arr[k-1]+1)
continue;
list.add(getRange(arr[k-1]+1, arr[k]-1));
}
if(arr[arr.length-1]!=end)
list.add(getRange(arr[arr.length-1]+1,end));
return list;
} //方法二
public List<String> getMissingRanges2(int[] arr,int start,int end){
List<String> list = new ArrayList<String>();
int pre=start-1;
for(int i=0;i<=arr.length;i++) {
int cur = (i==arr.length) ? end+1 : arr[i];
if(cur-pre>=2)
list.add(getRange(pre+1, cur-1));
pre=cur;
}
return list;
} private String getRange(int from, int to) {
return (from==to)? ""+from : from+"->"+to;
}
Complexity
Time complexity : O(n)
Space complexity : O(1)
What I've learned
1.数组为空时，应该返回[start->end]而不是返回null。
2.使用List<String>数据结构来返回返回缺失的数字范围。
3.方法二中pre和cur就是已知的数字，可以推得方法一中所要的缺失首尾，所以更加方便。
More:【目录】LeetCode Java实现
