摘要:双层迭代法复杂度时间空间思路外层的循环控制每个的起点,内层的循环控制之内的递增。每当遍历完一个,就把它记录到结果中,并更新下一个的起点。这里的技巧是,判断一个数是否是在内的,只要就行了,即值之差等于下标之差。
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 ListsummaryRanges(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; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64553.html
摘要:输入一个排序好的整数数组,输出数组中连续数字的范围的数组这是我的解法,不知道有没有有更好更快的实现 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]. 输入一个排...
摘要:想象一下假设数组前有一段连续的负无穷到,数组后有一段到正无穷,这样是等价与上下界的。最后循环到停止,当下标为时,我们将当前指针指向,并判断和数组末尾是否能构成最后一个区间。 Missing Ranges Given a sorted integer array where the range of elements are [lower, upper] inclusive, retu...
Summary Ranges 题目链接:https://leetcode.com/problems... loop两种写法: public class Solution { public List summaryRanges(int[] nums) { List result = new ArrayList(); if(nums.length == 0) r...
摘要:接着计算所有子数组中元素的和,并判断是否位于数值区间内。因此,在对左右子数组进行排序后,以左子数组中的每一位作为开头,在右子数组中找到满足和区间的第一个值,和超过区间的第一个值。则二者的差即为横穿左右的满足条件的子数组个数。 题目要求 Given an integer array nums, return the number of range sums that lie in [lo...
摘要:而产生这种现象的唯一远远,仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的,因此作为三个等权重的特征之一,飞行常客里程数并不应该如此严重的影响到计算结果。 一、KNN概述 简单的说,k-近邻算法采用测量不同特征值之间的距离方法进行分类。 优点:精度高、对异常值不敏感、无数据输入假定 缺点:计算复杂度高、空间复杂度高 适用数据范围:数值型和标称型 1.1 工...
阅读 1732·2021-11-24 10:18
阅读 2207·2021-11-18 13:20
阅读 2332·2021-08-23 09:46
阅读 992·2019-08-30 15:56
阅读 2839·2019-08-30 15:53
阅读 737·2019-08-30 14:22
阅读 470·2019-08-29 15:34
阅读 2531·2019-08-29 12:14