IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    [原]LeetCode Missing Ranges [LeetCode Book Problem]

    yangliuy发表于 2015-06-15 12:59:49
    love 0

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

    思路分析:这题基本就是考察双指针的应用,从lower-1开始,遍历nums数组找出missing range,可以利用pre和cur一前一后两个指针移动实现。注意lower和upper的处理,lower可以比nums中最小的数大,upper可以比nums中最大的数小,所以考虑要周全。

    参考Code(Book中的题目)

    public List findMissingRanges(int[] nums, int lower, int upper) {        
            List res = new ArrayList();
            int pre = lower - 1;
            for(int i = 0; i < nums.length; i++){
                if(i == nums.length){
                    cur = upper + 1;
                } else cur = nums[i];
                if(cur - pre >= 2){
                    int missStart = pre + 1;
                    int missEnd = cur - 1;
                    if(missEnd == missStart) res.add(missEnd);
                    else res.add(missStart + "->" + missEnd);
                    pre = cur;
                } else {
                    pre = cur;
                }
            }
            return res;
        }




沪ICP备19023445号-2号
友情链接