【数组】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、、、)

相关推荐

  1. 数组Leetcode 228. 汇总区间简单

    2024-05-25 19:36:29       34 阅读
  2. [leetcode] 228. 汇总区间

    2024-05-25 19:36:29       36 阅读
  3. 汇总区间算法(leetcode228题)

    2024-05-25 19:36:29       51 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-05-25 19:36:29       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-05-25 19:36:29       101 阅读
  3. 在Django里面运行非项目文件

    2024-05-25 19:36:29       82 阅读
  4. Python语言-面向对象

    2024-05-25 19:36:29       91 阅读

热门阅读

  1. CentOS防火墙管理及配置

    2024-05-25 19:36:29       28 阅读
  2. python 庆余年2收视率数据分析与可视化

    2024-05-25 19:36:29       29 阅读
  3. amis中 InputTable Combo InputKV/InputKVS 区别

    2024-05-25 19:36:29       30 阅读
  4. jupyter notebook 实现联邦学习模型

    2024-05-25 19:36:29       34 阅读
  5. android上用QT实现绘制曲线及双指放大缩小

    2024-05-25 19:36:29       30 阅读
  6. 接口作为返回类型与类作为返回类型一样吗?

    2024-05-25 19:36:29       32 阅读
  7. 微信小程序自定义头部

    2024-05-25 19:36:29       31 阅读
  8. Git 使用手册

    2024-05-25 19:36:29       31 阅读