[LeetCode] Missing Ranges | 程序员达达
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"]
https://leetcode.com/discuss/45508/accepted-java-solution-with-explanation
public List<String> findMissingRanges(int[] a, int lo, int hi) { List<String> res = new ArrayList<String>(); // the next number we need to find int next = lo; for (int i = 0; i < a.length; i++) { // not within the range yet if (a[i] < next) continue; // continue to find the next one if (a[i] == next) { next++; continue; } // get the missing range string format res.add(getRange(next, a[i] - 1)); // now we need to find the next number next = a[i] + 1; } // do a final check if (next <= hi) res.add(getRange(next, hi)); return res; } String getRange(int n1, int n2) { return (n1 == n2) ? String.valueOf(n1) : String.format("%d->%d", n1, n2); }
http://segmentfault.com/a/1190000003790309
http://buttercola.blogspot.com/2015/08/leetcode-missing-ranges.html
The problem itself is not hard at all. The key is to handle several corner cases. e.g.
-- If the array is empty, the missing ranges should be from lower to upper, inclusive.
-- For the leading missing range, e.g. -2 , [-1], -1. The output should be "-2". Note that the lower bound is inclusive.
-- For the trailing missing range, e.g. -2, [-2], 1, the output should be "-1->1". The upper bound is inclusive as well.
这道题其实不难，但是就是要考虑清楚各种情况。根据题意，[lower, upper]一定是包含这个array所有元素的，不会存在不包含甚至没有交集的情况。只是要特别考虑一下A[0]和lower的关系， 以及A[N]与upper的关系，它们所以存在的情况：
1. lower == A[0] && upper == A[N]
2. lower < A[0] && upper == A[N]
3. lower == A[0] && upper > A[N]
4. lower < A[0] && upper > A[N]
整体来说，需要考虑如下所有case：
1. 为空，lower 与 upper 之间关系。
2. lower 与 A[0] 之间关系
3. A[i]~A[i+1] 之间关系
4 A[A.length-1] 与 upper 之间关系
--Extract functions.
每看一个数字，表示之前的都处理完了。
最后再处理 最后面一个数字。
http://www.cnblogs.com/EdwardLiu/p/4249626.html
Read full article from [LeetCode] Missing Ranges | 程序员达达
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"]
https://leetcode.com/discuss/45508/accepted-java-solution-with-explanation
public List<String> findMissingRanges(int[] a, int lo, int hi) { List<String> res = new ArrayList<String>(); // the next number we need to find int next = lo; for (int i = 0; i < a.length; i++) { // not within the range yet if (a[i] < next) continue; // continue to find the next one if (a[i] == next) { next++; continue; } // get the missing range string format res.add(getRange(next, a[i] - 1)); // now we need to find the next number next = a[i] + 1; } // do a final check if (next <= hi) res.add(getRange(next, hi)); return res; } String getRange(int n1, int n2) { return (n1 == n2) ? String.valueOf(n1) : String.format("%d->%d", n1, n2); }
http://segmentfault.com/a/1190000003790309
我们用一个指针prev记录上次range的结尾，一个指针curr记录当前遍历到的数字，如果curr和prev相差大于1，说明一个missing range，我们将其加入结果列表中就行了。这题主要是有几个corner case要解决：
- 如何处理lower到第一个数，和最后一个数到upper的missing range？
- 如何区分range中只有一个数和多个数？
- 如何有效的得到missing range的起始和结束值，同时保证不会包含数组中的数字？
对于第一个问题，我们要做的就是在让for循环多判断两次。想象一下假设数组前有一段连续的负无穷到lower-1，数组后有一段upper+1到正无穷，这样是等价与上下界的。本来如果不考虑头尾，那for循环本应是从1到length-1的，但是为了判断头，我们从0开始，将下标为0的数和lower-1比较得到第一个range。最后循环到length停止，当下标为length时，我们将当前指针指向upper+1，并判断upper+1和数组末尾是否能构成最后一个区间。
对于第二个问题，我们只要判断这个区间的起止是否一样就行了
对于第三个问题，我们用prev+1和curr-1来标记这个区间的起止，因为prev和curr都是数组中的数，所以解决了每个区间的边界问题
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> res = new LinkedList<String>();
// 初始化prev为lower-1，判断是否存在“第一个”区间
int prev = lower - 1, curr = 0;
for(int i = 0 ; i <= nums.length; i++){
// 当遍历到length时，设置curr为upper+1，判断是否存在“最后一个”区间
curr = i == nums.length ? upper + 1 : nums[i];
// 如果上一个数和当前数相差大于1，说明之间有区间
if(curr - prev > 1){
res.add(getRanges(prev+1, curr-1));
}
prev = curr;
}
return res;
}
private String getRanges(int from, int to){
return from == to ? String.valueOf(from) : from + "->" + to;
}http://buttercola.blogspot.com/2015/08/leetcode-missing-ranges.html
The problem itself is not hard at all. The key is to handle several corner cases. e.g.
-- If the array is empty, the missing ranges should be from lower to upper, inclusive.
-- For the leading missing range, e.g. -2 , [-1], -1. The output should be "-2". Note that the lower bound is inclusive.
-- For the trailing missing range, e.g. -2, [-2], 1, the output should be "-1->1". The upper bound is inclusive as well.
public List<String> findMissingRanges(int[] nums, int lower, int upper) { List<String> result = new ArrayList<String>(); if (nums == null || nums.length == 0) { outputToResult(lower, upper, result); return result; } // leading missing range if (nums[0] - lower > 0) { outputToResult(lower, nums[0] - 1, result); } for (int i = 1; i < nums.length; i++) { if (nums[i] - nums[i - 1] > 1) { outputToResult(nums[i - 1] + 1, nums[i] - 1, result); } } // trailing missage ranges if (upper - nums[nums.length - 1] > 0) { outputToResult(nums[nums.length - 1] + 1, upper, result); } return result; } private void outputToResult(int start, int end, List<String> result) { StringBuffer sb = new StringBuffer(); if (start == end) { sb.append(start); } else { sb.append(start + "->" + end); } result.add(sb.toString()); }这道题其实不难，但是就是要考虑清楚各种情况。根据题意，[lower, upper]一定是包含这个array所有元素的，不会存在不包含甚至没有交集的情况。只是要特别考虑一下A[0]和lower的关系， 以及A[N]与upper的关系，它们所以存在的情况：
1. lower == A[0] && upper == A[N]
2. lower < A[0] && upper == A[N]
3. lower == A[0] && upper > A[N]
4. lower < A[0] && upper > A[N]
整体来说，需要考虑如下所有case：
1. 为空，lower 与 upper 之间关系。
2. lower 与 A[0] 之间关系
3. A[i]~A[i+1] 之间关系
4 A[A.length-1] 与 upper 之间关系
--Extract functions.
public List<String> findMissingRanges(int[] A, int lower, int upper) { ArrayList<String> res = new ArrayList<String>(); if (A.length == 0) { if (lower != upper) { res.add(Integer.toString(lower) + "->" + Integer.toString(upper)); } else { res.add(Integer.toString(lower)); } return res; } if (lower < A[0]) { if (lower == A[0] - 1) { res.add(Integer.toString(lower)); } else { res.add(Integer.toString(lower) + "->" + Integer.toString(A[0]-1)); } } for (int i=0; i<A.length-1; i++) { if (A[i+1] - A[i] > 2) { res.add(Integer.toString(A[i]+1) + "->" + Integer.toString(A[i+1]-1)); } else if (A[i+1] - A[i] == 2) { res.add(Integer.toString(A[i]+1)); } else continue; } if (upper > A[A.length-1]) { if (upper == A[A.length-1] + 1) { res.add(Integer.toString(upper)); } else { res.add(Integer.toString(A[A.length-1]+1) + "->" + Integer.toString(upper)); } } return res; }
public List<String> findMissingRanges(int[] vals, int start, int end) { List<String> ranges = new ArrayList<String>(); int prev = start - 1; for (int i=0; i<=vals.length; ++i) { int curr = (i==vals.length) ? end + 1 : vals[i]; if ( cur-prev>=2 ) { ranges.add(getRange(prev+1, curr-1)); } rev = curr; } return ranges; } private String getRange(int from, int to) { return (from==to) ? String.valueOf(from) : from + "->" to; }http://leetcode0.blogspot.com/2015/03/missing-ranges.html
每看一个数字，表示之前的都处理完了。
最后再处理 最后面一个数字。
public List<String> findMissingRanges(int[] A, int lower, int upper) { // assume all elements in A are in range (lower, upper) List<String> list = new LinkedList(); for(int i =0;i<A.length;i++){ if(lower>upper) // not used break; if(A[i] == lower){ lower++; }else if(A[i] >lower){ // add from lower to A[i]; String tmp = ""+lower; if(lower+1!=A[i]) tmp += "->"+ (A[i]-1); list.add(tmp); lower = A[i]+1; } } // check the last element if(lower <= upper){ String tmp = ""+lower; if(lower != upper) tmp += "->"+upper; list.add(tmp); } return list; } public List<String> findMissingRanges(int[] nums, int lower, int upper) { List<String> list = new LinkedList(); for(int i =0;i<nums.length; i++){ int val = nums[i]; if(val>lower){ String range = getRange(lower,Math.min(val-1,upper)) ; if(range.length()>0) list.add(range); lower=val+1; }else if(val == lower){ lower++; } } if(lower<=upper){ list.add(getRange(lower,upper)); } return list; } private String getRange(int start, int end){ if(start>end) return ""; else if(start==end) return ""+start; else return ""+start+"->"+end; }Read full article from [LeetCode] Missing Ranges | 程序员达达
