leetcode算法228.汇总区间



哈喽！大家好，我是【学无止境小奇】，一位热爱分享各种技术的博主！

⭐【学无止境小奇】的创作宗旨：每一条命令都亲自执行过，每一行代码都实际运行过，每一种方法都真实实践过，每一篇文章都良心制作过。✊✊✊

⭐【学无止境小奇】的博客中所有涉及命令、代码的地方，除了提供图片供大家参考，另外会在图片下方提供一份纯文本格式的命令或者代码方便大家粘贴复制直接执行命令或者运行代码。欄欄欄

⭐如果你对技术有着浓厚的兴趣，欢迎关注【学无止境小奇】，欢迎大家和我一起交流。

❤️❤️❤️感谢各位朋友接下来的阅读❤️❤️❤️

一、leetcode算法

1、汇总区间

1.1、题目1.2、思路1.3、答案

给定一个 无重复元素 的 有序 整数数组 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”

思路一：此题我们可以对数据进行一次遍历，从左向右开始遍历，判断相邻两个数是否差值为1，如果为1则加入字符串“->”,如果不为1,则进行单独插入。

class Solution {
    public List summaryRanges(int[] nums) {
        List ret = new ArrayList();
        int i = 0;
        int n = nums.length;
        while(i < n){
            int low = i;
            i++;
            //如果相连的数据都大于1则循环
            while(i < n && nums[i] == nums[i - 1] + 1){
                i++;
            }
            int high = i - 1;
            StringBuffer temp = new StringBuffer(Integer.toString(nums[low]));
            if(low < high){
                temp.append("->");
                temp.append(Integer.toString(nums[high]));
            }
            ret.add(temp.toString());
        }
        return ret;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为数组的长度。

空间复杂度：O(1)。除了用于输出的空间外，额外使用的空间为常数。