Leetcode: Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, 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"].

第二遍做法：参考下面一个vimukthi的解答 https://discuss.leetcode.com/topic/18612/accepted-java-solution-with-explanation/3

low 表示next possible missing integer streak的start, justBelow表示next possible missing range的end，因为+-可能溢出，所以选择long type

 1 public class Solution {
 2     public List<String> findMissingRanges(int[] nums, int lower, int upper) {
 3         List<String> list = new ArrayList<String>();
 4         long low = lower; // use low as the start of next possible missing range
 5         long up = upper;
 6         for(int n : nums){
 7             long justBelow = (long)n - 1; // the end of next possible missing range
 8             if(low == justBelow) list.add(low+""); //low is the start of the next possible missing range
 9             else if(low < justBelow) list.add(low + "->" + justBelow);
10             low = (long)n + 1; //update low to be the start of next possible missing range
11         }
12         if(low == up) list.add(low+"");
13         else if(low < up) list.add(low + "->" + up);
14         return list;
15     }
16 }

Follow Up: 如果lower可能大于array中部分元素，upper也可能小于部分元素怎么办？

直接skip掉

 1 package GooglePhone;
 2 
 3 import java.util.*;
 4 
 5 public class MissingRanges {
 6 
 7         public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
 8             List<String> list = new ArrayList<String>();
 9             for(int n : nums){
10                 if (n < lower) continue;
11                 if (n > upper) continue;
12                 int justBelow = n - 1;
13                 if(lower == justBelow) list.add(lower+"");
14                 else if(lower < justBelow) list.add(lower + "->" + justBelow);
15                 lower = n+1;
16             }
17             if(lower == upper) list.add(lower+"");
18             else if(lower < upper) list.add(lower + "->" + upper);
19             return list;
20         }
21     /**
22      * @param args
23      */
24     public static void main(String[] args) {
25         // TODO Auto-generated method stub
26         List<String> res = findMissingRanges(new int[]{1,5,7,8,11,12,20}, 0, 10);
27         System.out.println(res);
28     }
29 
30 }

第一遍做法：这道题其实不难，但是就是要考虑清楚各种情况。根据题意，[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 之间关系

public class Solution {  
    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;
    }
}