[Leetcode] Summary Ranges 统计区间

Youngdze 发布于2019-08-14 12:33 / 1626人阅读

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

Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

双层迭代法 复杂度

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

思路

外层的while循环控制每个range的起点，内层的while循环控制range之内的递增。每当遍历完一个range，就把它记录到结果中，并更新下一个range的起点。这里的技巧是，判断一个数是否是在range内的，只要nums[start + range] - nums[start] = range就行了，即值之差等于下标之差。

代码

public class Solution {
    public List summaryRanges(int[] nums) {
        List res = new LinkedList();
        if(nums.length == 0) return res;
        StringBuilder tmp = new StringBuilder();
        int start = 0;
        while(start < nums.length){
            int range = 1;
            // 遍历当前range内的所有数
            while(start + range < nums.length && (nums[start + range] - nums[start]) == range){
                range++;
            }
            // 遍历完了当前range，将其加入结果中
            tmp.append(nums[start]);
            if(range > 1){
                tmp.append("->");
                tmp.append(nums[start+range-1]);
            }
            res.add(tmp.toString());
            tmp = new StringBuilder();
            // 更新下一个range的起点
            start = start + range;
        }
        return res;
    }
}

GPU云服务器云服务器 Ranges summary LeetCode LeetCode_String

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

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

［Leetcode刷题］Summary Ranges —— javascript

摘要：输入一个排序好的整数数组，输出数组中连续数字的范围的数组这是我的解法，不知道有没有有更好更快的实现 Given a sorted integer array without duplicates, return the summary of its ranges. For example, given [0,1,2,4,5,7], return [0->2,4->5,7]. 输入一个排...

Doyle 2019-08-19 18:33 评论0 收藏0
[Leetcode] Missing Ranges 缺失区间

摘要：想象一下假设数组前有一段连续的负无穷到，数组后有一段到正无穷，这样是等价与上下界的。最后循环到停止，当下标为时，我们将当前指针指向，并判断和数组末尾是否能构成最后一个区间。 Missing Ranges Given a sorted integer array where the range of elements are [lower, upper] inclusive, retu...

Gilbertat 2019-08-14 12:36 评论0 收藏0
Summary Ranges

Summary Ranges 题目链接：https://leetcode.com/problems... loop两种写法： public class Solution { public List summaryRanges(int[] nums) { List result = new ArrayList(); if(nums.length == 0) r...

yintaolaowanzi 2019-08-14 17:22 评论0 收藏0
leetcode327. Count of Range Sum

摘要：接着计算所有子数组中元素的和，并判断是否位于数值区间内。因此，在对左右子数组进行排序后，以左子数组中的每一位作为开头，在右子数组中找到满足和区间的第一个值，和超过区间的第一个值。则二者的差即为横穿左右的满足条件的子数组个数。题目要求 Given an integer array nums, return the number of range sums that lie in [lo...

miya 2019-08-16 16:47 评论0 收藏0
K Nearest Neighbor

摘要：而产生这种现象的唯一远远，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重的影响到计算结果。一、KNN概述简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。优点：精度高、对异常值不敏感、无数据输入假定缺点：计算复杂度高、空间复杂度高适用数据范围：数值型和标称型 1.1 工...

zzbo 2019-07-31 11:30 评论0 收藏0