2015年9月10日星期四

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"].

public class Solution {
    // [] -1 -1
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<String>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < lower) {
                continue;
            } else if (nums[i] == lower) {
                lower++;
            } else {
                int from = lower;
                int to = Math.min(upper, nums[i] - 1);
                if (from == to) {
                    res.add(Integer.toString(from));
                } else {
                    res.add(from + "->" + to);
                }
                lower = nums[i] + 1;
            }
            if (lower > upper) {
                break;
            }
        }
        if (lower <= upper) {
            int from = lower;
            int to = upper;
            if (from == to) {
                res.add(Integer.toString(from));
            } else {
                res.add(from + "->" + to);
            }
        }
        return res;
    }
}
================

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            addRange(lower, upper, res);
            return res;
        }
        for (int n : nums) {
            if (n == lower) {
                lower++;
            } else {
                addRange(lower, Math.min(upper, n - 1), res);
                lower = n + 1;
            }
            if (lower > upper) break;
        }
        addRange(lower, upper, res);
        return res;
    }
   
    private void addRange(int from, int to, List<String> res) {
        if (from == to) {
            res.add(Integer.toString(from));
        } else if (from < to) {
            res.add(from + "->" + to);
        }
    }
}

没有评论:

发表评论