Leetcode 163. Missing Ranges

作者: ShutLove | 来源:发表于2017-11-06 18:06 被阅读19次

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

    思路:
    查看每个数字和上一个数字中是否需要补区间,第一个数字需要和lower做比较,最后一个数字还要和upper做一次比较。
    此题坑较多:比如low和up相同,数组为空的case;low和up是int类型的最小和最大值的情况,此时用num[i] - num[i-1]就会有溢出。

    public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            String range = "";
            if (lower == upper) {
                range = String.valueOf(lower);
            } else {
                range = String.valueOf(lower) + "->" + String.valueOf(upper);
            }
            //String range = String.valueOf(lower) + "->" + String.valueOf(upper);//bug
            res.add(range);
            return res;
        }
    
        for (int i = 0; i < nums.length; i++) {
            String range = "";
            //if (i == 0 && nums[i] > lower) {//bug//第一个和lower比
            if (i == 0) {//第一个和lower比
                if (nums[i] > lower) {
                    if (nums[i] - 1 == lower) {
                        range = String.valueOf(lower);
                    } else {
                        range = String.valueOf(lower) + "->" + String.valueOf(nums[i] - 1);
                    }
                }
            } else {
                long diff = (long)nums[i] - (long)nums[i-1];
                System.out.println(diff);
                if (diff == 2) {//其余的和前一个比
                    range = String.valueOf(nums[i] - 1);
                } else if (diff > 2) {
                    range = String.valueOf(nums[i-1] + 1) + "->" + String.valueOf(nums[i] - 1);
                }
            }
            if (!range.equals("")) {
                res.add(range);
            }
            //res.add(range);//bug 会向res重复add range
    
            if (i == nums.length - 1 && nums[i] < upper) {//最后一个再和upper比一次
                if (upper - 1 == nums[i]) {
                    range = String.valueOf(upper);
                } else {
                    range = String.valueOf(nums[i] + 1) + "->" + String.valueOf(upper);
                }
                res.add(range);
            }
            //res.add(range); //bug 会向res重复add range
        }
    
        return res;
    }

    相关文章

      网友评论

        本文标题:Leetcode 163. Missing Ranges

        本文链接:https://www.haomeiwen.com/subject/mqnlmxtx.html