Leetcode - MissingRange

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”]

[TIPS] 1.特殊情况向面试官确认，数组为空或者包含全部元素返回什么

2. 注意可扩展性，题意为[0,99]，扩展为[start, end]
3 findMissingRanges2方法未在online上跑过，简单自测， findMissingRanges转载自链接以备忘，
优点在于无需额外处理特殊情形

 

    public List<String> findMissingRanges2(int[] vals, int start, int end) {
        List<String> ranges = new ArrayList<String>();
        if (vals == null || vals.length == 0) {
            ranges.add(start + "->" + end);
            return ranges;
        }
        // int need = 0; // 如果start ！= 0 就错了
        int need = start;
        for (int i = 0; i < vals.length; i++) {
            if (vals[i] > need) {
                ranges.add(getRange(need, vals[i] - 1));
            }
            need = vals[i] + 1;
        }
        if (need <= end)
            ranges.add(getRange(need, end));
        return ranges;
    }

    // 转载：http://www.danielbit.com/blog/puzzle/leetcode/leetcode-missing-ranges
    public List<String> findMissingRanges(int[] vals, int start, int end) {
        List<String> ranges = new ArrayList<String>();
        if (vals == null || vals.length == 0) {
            ranges.add(start + "->" + end);
            return ranges;
        }
        int prev = start - 1;
        for (int i = 0; i <= vals.length; i++) {
            int curr = (i == vals.length) ? end + 1 : vals[i];
            if (curr - prev >= 2) {
                ranges.add(getRange(prev + 1, curr - 1));
            }
            prev = curr;
        }
        return ranges;
    }

    private String getRange(int from, int to) {
        return (from == to) ? String.valueOf(from) : from + "->" + to;
    }

 

评论

1 楼 qb_2008 2015-04-01  

line 7: int need = start;