228. Summary Ranges

228. Summary Rangesopen in new window

🟢 🔖 数组 🔗 LeetCodeopen in new window

题目

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

"a->b" if a != b
"a" if a == b

Example 1:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Example 2:

Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

Constraints:

0 <= nums.length <= 20
-2^31 <= nums[i] <= 2^31 - 1
All the values of nums are unique.
nums is sorted in ascending order.

题目大意

给定一个 无重复元素 的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

"a->b" ，如果 a != b
"a" ，如果 a == b

解题思路

因为数组是有序的，可以遍历数组里的每个数 i ，以其为起点，寻找 i+1, i+2, i+3...是否存在，并不断记录：
- 若 i+1 不存在，直接将 i 加入返回数组中；
- 若 i+1 存在，则以 i 为起点开始枚举，直到 i + n 不存在时，再将 i + '->' + (i + n - 1) 加入返回数组中；
为了降低遍历数组的时间复杂度，可以将数组中的数存在哈希表中，这样查看一个数是否存在的时间复杂度可以优化到 O(1)；

代码

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function (nums) {
	let set = new Set(nums),
		res = [];
	for (let i = 0; i < nums.length; i++) {
		let num = nums[i],
			str = '' + num;
		if (!set.has(num + 1)) {
			res.push(str);
		} else {
			let len = 1;
			while (set.has(num + len)) {
				len++;
				i++;
			}
			res.push(str + '->' + (num + len - 1));
		}
	}
	return res;
};

228. Summary Ranges

# 228. Summary Rangesopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

228. Summary Rangesopen in new window

题目

题目大意

解题思路

代码

相关题目