[Leetcode] Missing Ranges 缺失区间

Gilbertat 发布于2019-08-14 12:36 / 2203人阅读

摘要：想象一下假设数组前有一段连续的负无穷到，数组后有一段到正无穷，这样是等价与上下界的。最后循环到停止，当下标为时，我们将当前指针指向，并判断和数组末尾是否能构成最后一个区间。

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

双指针遍历 复杂度

时间 O(N) 空间 O(1)

思路

我们用一个指针prev记录上次range的结尾，一个指针curr记录当前遍历到的数字，如果curr和prev相差大于1，说明一个missing range，我们将其加入结果列表中就行了。这题主要是有几个corner case要解决：

如何处理lower到第一个数，和最后一个数到upper的missing range？

如何区分range中只有一个数和多个数？

如何有效的得到missing range的起始和结束值，同时保证不会包含数组中的数字？

对于第一个问题，我们要做的就是在让for循环多判断两次。想象一下假设数组前有一段连续的负无穷到lower-1，数组后有一段upper+1到正无穷，这样是等价与上下界的。本来如果不考虑头尾，那for循环本应是从1到length-1的，但是为了判断头，我们从0开始，将下标为0的数和lower-1比较得到第一个range。最后循环到length停止，当下标为length时，我们将当前指针指向upper+1，并判断upper+1和数组末尾是否能构成最后一个区间。

对于第二个问题，我们只要判断这个区间的起止是否一样就行了

对于第三个问题，我们用prev+1和curr-1来标记这个区间的起止，因为prev和curr都是数组中的数，所以解决了每个区间的边界问题

代码

public class Solution {
    public List findMissingRanges(int[] nums, int lower, int upper) {
        List res = new LinkedList();
        // 初始化prev为lower-1，判断是否存在“第一个”区间
        int prev = lower - 1, curr = 0;
        for(int i = 0 ; i <= nums.length; i++){
            // 当遍历到length时，设置curr为upper+1，判断是否存在“最后一个”区间
            curr = i == nums.length ? upper + 1 : nums[i];
            // 如果上一个数和当前数相差大于1，说明之间有区间
            if(curr - prev > 1){
                res.add(getRanges(prev+1, curr-1));
            }
            prev = curr;
        }
        return res;
    }
    
    private String getRanges(int from, int to){
        return from == to ? String.valueOf(from) : from + "->" + to;
    }
}

云服务器 GPU云服务器 Ranges missing LeetCode method_missing

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64590.html

[Leetcode] Summary Ranges 统计区间

摘要：双层迭代法复杂度时间空间思路外层的循环控制每个的起点，内层的循环控制之内的递增。每当遍历完一个，就把它记录到结果中，并更新下一个的起点。这里的技巧是，判断一个数是否是在内的，只要就行了，即值之差等于下标之差。 Summary Ranges Given a sorted integer array without duplicates, return the summary of it...

Youngdze 2019-08-14 12:33 评论0 收藏0
[Leetcode] Missing Number and Missing First Positi

摘要：代码映射法复杂度时间空间思路核心思想就是遍历数组时，将每个元素，和以该元素为下标的元素进行置换，比如第一个元素是，就将它置换到下标为的地方，而原本下标为的地方的元素就换到第一个来。 Missing Number Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one t...

Forest10 2019-08-14 12:24 评论0 收藏0
LeetCode 之 JavaScript 解答第41题 —— 缺失的第一个正数（First Mis

摘要：小鹿题目算法思路桶排序思想。再遍历数组，从下标开始判断该下标是否存放规定的数据，如果不是则该下标就是这组数据中缺失的最小正整数。桶排序还可以实现在一组数据中查找重复的数据。 Time：2019/4/6Title: First Missing PositiveDifficulty: DifficultyAuthor: 小鹿题目：First Missing Positive Give...

levius 2019-08-23 16:46 评论0 收藏0
orm2 中文文档 3.2 模型验证器

摘要：译者飞龙来源模块用于验证数据。可用的验证器的列表请见。验证器也构建于中，可以这样来访问你可以为模型的每个属性定义验证器。在第一个验证器验证失败之后，验证就停止了。译者：飞龙来源：Model Validations Enforce模块用于验证数据。对于使用以前的验证器的用户，还可以继续使用，它们中的一部分整合到了enforce，剩余部分还没有。推荐你开始使用orm.enforce...

zhiwei 2019-06-25 18:18 评论0 收藏0