Skip to content

Latest commit

 

History

History
86 lines (70 loc) · 2.54 KB

228-SummaryRanges.md

File metadata and controls

86 lines (70 loc) · 2.54 KB

汇总区间

给定一个 无重复元素 的 有序 整数数组 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^31 <= nums[i] <= 2^31 - 1
  • nums 中的所有值都 互不相同
  • nums 按升序排列

思路:

  1. 初始化结果数组:ret 用于存储最终的区间字符串。
  2. 外层循环:遍历数组 nums,使用变量 i 作为索引。
  3. 确定区间起点:当 i 指向一个新区间的起点时,记录这个位置 low。
  4. 扩展区间:内层循环尝试将当前区间向后扩展,直到遇到不连续的数字。如果下一个数字比当前数字大 1,说明仍然在同一区间内,继续向后扩展。
  5. 确定区间终点:当无法继续扩展区间时,记录区间的终点 high。
  6. 构建区间字符串:
    • 如果区间只包含一个数字(low 等于 high),则直接将该数字作为区间字符串。
    • 如果区间包含多个数字(low 小于 high),则构建形如 "a->b" 的字符串,其中 a 是区间起点,b 是区间终点。
  7. 添加到结果数组:将构建好的区间字符串添加到结果数组 ret 中。
  8. 返回结果:遍历结束后,返回结果数组 ret。

时间复杂度:O(n),其中 n 是数组 nums 的长度。算法需要遍历数组中的每个元素一次。 空间复杂度:O(m),其中 m 是结果数组 ret 的长度,最坏情况下,每个元素都形成一个单独的区间。

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function (nums) {
  const ret = [];
  let i = 0;
  const n = nums.length;

  while (i < n) {
    const low = i;
    // 扩展区间
    while (i + 1 < n && nums[i + 1] === nums[i] + 1) {
      i++;
    }
    const high = i;
    // 构建区间字符串
    if (low === high) {
      ret.push(nums[low].toString());
    } else {
      ret.push(`${nums[low]}->${nums[high]}`);
    }
    i++;
  }

  return ret;
};