BiruLyu
8/4/2017 - 6:43 PM

163. Missing Ranges(#).java

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> list = new ArrayList<String>();
        int preMiss = lower;
        for (int num : nums) {
            if (num == Integer.MAX_VALUE) {
                if (upper == num)
                    --upper;
                break;
            }
            preMiss = getNext(preMiss, num, list);
        }
        //handle anything not in the array that lower than the upper.
        if (preMiss == upper)
            list.add(preMiss + "");
        else if (preMiss < upper)
            list.add(preMiss + "->" + upper);
        return list;
    }

    private static int getNext(int miss, int num, List<String> list) {
        if (miss < num) {
            if (miss == num - 1)
                list.add(miss + "");
            else
                list.add(miss + "->" + (num - 1));
        }
        return num + 1;
    }
}
public class Solution {
    private String interval(int start, int end) {
        if (start == end) {
            return String.valueOf(start);
        }
        return start + "->" + end;
    }
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            res.add(interval(lower,upper));
            return res;
        } 
        int len = nums.length;
        if (lower - nums[0] != 0) {
            int start = lower;
            int end = nums[0] - 1;
            res.add(interval(start, end));
        }
        for (int i = 1; i < len; i++) {
            if (nums[i] == nums[i - 1]) continue; // [1,1,1]
            if (nums[i] != nums[i - 1] + 1) {
                int start = nums[i - 1] + 1;
                int end = nums[i] - 1;
                res.add(interval(start, end));
            }
        }
        if (upper - nums[len - 1] != 0) {
            int start = nums[len - 1] + 1;
            int end = upper;
            res.add(interval(start, end));
        }
        return res;
    }
}