【数组】Leetcode 228. 汇总区间【简单】
汇总区间
-
给定一个 无重复元素 的 有序 整数数组 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”
解题思路
- 遍历数组时，识别连续的数字段，将其作为一个区间，并将区间转换为所需的字符串格式。
Java实现
public class SummaryRanges {public List<String> summaryRanges(int[] nums) {List<String> ranges = new ArrayList<>();int n = nums.length;if (n == 0) {return ranges;}int start = nums[0];int end = nums[0];for (int i = 1; i < n; i++) {if (nums[i] == end + 1) {end = nums[i];} else {//判断是否是单个数字不连续if (start == end) {ranges.add(String.valueOf(start));} else {//否则，是多个数字 后续不再连续ranges.add(start + "->" + end);}start = nums[i];end = nums[i];}}//最后范围只做了赋值操作，并没有做添加操作，添加最后范围if (start == end) {ranges.add(String.valueOf(start));} else {ranges.add(start + "->" + end);}return ranges;}public static void main(String[] args) {SummaryRanges sr = new SummaryRanges();int[] nums1 = {0, 1, 2, 4, 5, 7};int[] nums2 = {0, 2, 3, 4, 6, 8, 9};System.out.println(sr.summaryRanges(nums1)); // 输出: ["0->2", "4->5", "7"]System.out.println(sr.summaryRanges(nums2)); // 输出: ["0", "2->4", "6", "8->9"]}
}时间空间复杂度
- 时间复杂度: O(n)，其中 n 是数组 nums 的长度。只需要遍历一次数组，因此时间复杂度是线性的。
- 空间复杂度: O(1)到O(n)，除了用于存储结果的列表 ranges 最差为O(n/2),即(1、3、5、7、、、)最好为O(1),即（1、2、3、4、、、）