228. 汇总区间
难度: 简单
来源: 每日一题 2023.08.26
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums
的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums
的数字 x
。
列表中的每个区间范围 [a,b]
应该按如下格式输出:
"a->b"
,如果a != b
"a"
,如果a == b
示例 1:
输入:nums = [0,1,2,4,5,7]
输出:["0->2","4->5","7"]
解释:区间范围是:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
示例 2:
输入:nums = [0,2,3,4,6,8,9]
输出:["0","2->4","6","8->9"]
解释:区间范围是:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
提示:
0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums
中的所有值都 互不相同nums
按升序排列
class Solution {
public int alternateDigitSum(int n) {
}
}
分析与题解
-
双指针 + 遍历
这个问题求区间, 其实我们需要使用两个指针来标明区间的起始位置和结束位置. 那么什么时机我们需要输出一个区间呢? 主要有以下几种情况.
-
当
下一个数值
比当前数值
大于1时. -
当遍历到尾部的时候.
if (i != nums.length - 1) { if (nums[i] + 1 < nums[i+1]) { end = i; } } else { end = nums.length - 1; }
然后, 生成区间的条件条件就根据题目说明的来即可.
-
"a->b"
,如果a != b
-
"a"
,如果a == b
if (end != -1) { if (start == end) { result.add("" + nums[i]); } else { result.add(nums[start] + "->" + nums[end]); } end = -1; start = i + 1; }
整体如下所示.
class Solution { public List<String> summaryRanges(int[] nums) { List<String> result = new ArrayList<String>(); if(nums.length == 0) { return result; } int start = 0; int end = -1; for(int i = 0; i < nums.length; i++) { if (i != nums.length - 1) { if (nums[i] + 1 < nums[i+1]) { end = i; } } else { end = nums.length - 1; } if (end != -1) { if (start == end) { result.add("" + nums[i]); } else { result.add(nums[start] + "->" + nums[end]); } end = -1; start = i + 1; } } return result; } }
复杂度分析:
- 时间复杂度: O(n). 需要遍历一次.
- 空间复杂度: O(1), 不算返回List的空间, 其他空间为常量级别的空间
结果如下所示.
-
Comments | 0 条评论