汇总区间

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"

示例 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
-2³¹ <= nums[i] <= 2³¹ - 1
nums 中的所有值都 互不相同
nums 按升序排列

相似题目

缺失的区间

将数据流变为多个不相交区间

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<string> summaryRanges(vector<int>& nums) { } };

javascript 解法, 执行用时: 56 ms, 内存消耗: 41.1 MB, 提交时间: 2023-08-26 08:34:04

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function(nums) {
    const ret = [];
    let i = 0;
    const n = nums.length;
    while (i < n) {
        const low = i;
        i++;
        while (i < n && nums[i] === nums[i - 1] + 1) {
            i++;
        }
        const high = i - 1;
        const temp = ['' + nums[low]];
        if (low < high) {
            temp.push('->');
            temp.push('' + nums[high]);
        }
        ret.push(temp.join(''));
    }
    return ret;
};

java 解法, 执行用时: 0 ms, 内存消耗: 39.5 MB, 提交时间: 2023-08-26 08:33:44

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ret = new ArrayList<String>();
        int i = 0;
        int n = nums.length;
        while (i < n) {
            int low = i;
            i++;
            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;
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2020-11-20 14:25:21

func summaryRanges(nums []int) []string {
    n := len(nums)
    var ans []string
    if n == 0 {
        return ans
    }
    start, end := nums[0], nums[0]
    for i := 1; i < n; i++ {
        if nums[i] - nums[i-1] == 1 {
            end = nums[i]
        } else {
            ans = append(ans, helper(start, end))
            start = nums[i]
        }
    }
    ans = append(ans, helper(start, end))
    return ans
}

func helper(start, end int) string {
    if start < end {
        return fmt.Sprintf("%d->%d", start, end)
    }
    return fmt.Sprintf("%d", start)
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2020-11-20 11:33:29

func summaryRanges(nums []int) []string {
    n := len(nums)
    var ans []string
    if n == 0 {
        return ans
    }
    start, end := nums[0], nums[0]
    for i := 1; i < n; i++ {
        if nums[i] - nums[i-1] == 1 {
            end = nums[i]
        } else {
            if start < end {
                ans = append(ans, fmt.Sprintf("%d->%d", start, end))
            } else {
                ans = append(ans, fmt.Sprintf("%d", start))
            }
            start = nums[i]
        }
    }
    if start < end {
        ans = append(ans, fmt.Sprintf("%d->%d", start, end))
    } else {
        ans = append(ans, fmt.Sprintf("%d", start))
    }    

    return ans
}

python3 解法, 执行用时: 40 ms, 内存消耗: 13.6 MB, 提交时间: 2020-11-20 11:28:42

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        n, ans = len(nums), []
        if n == 0:
            return ans
        start, end = nums[0], nums[0]
        for i in range(1, n):
            if nums[i] - nums[i-1] == 1:
                end = nums[i]
            else:
                ans.append(f'{start}->{end}' if end > start else f'{start}')
                start = nums[i]
        ans.append(f'{start}->{end}' if end > start else f'{start}')
        return ans

上一题

下一题

详情