【面试经典150 | 区间】汇总区间

Tag

【一次遍历】【数组】【字符串】

---

题目来源

228. 汇总区间

---

题目解读

给定一个无重复的升序数组 nums，需要将这个数组按照以下规则进行汇总：

• 对于数组中的连续整数，比如0, 1, 2，输出连续区间"0->2"；
• 对于数组中的非连续整数，比如数组[0, 1, 2, 4]中的4，输出单独区间"4"。

最后输出数组nums的汇总字符串。

---

解题思路

数据规模很小，时间复杂度上无需担心。

但是，数组中的数据值可能会取到int整型数据的边界处，边界处的+-*/计算容易越界，需要小心。比如 -2147483647 - -2147483648就会报错。

方法一：一次遍历

从数组0位置出发，向右遍历。使用start指针记录连续元素的起始值，end记录连续元素的终点值，在遍历中动态维护两个指针，在遍历过程中：

• 如果start != end，则输出字符串"start->end"；
• 如果start == end，则表明该数字不属于任何连续的区间，需要作为一个单独的区间元素输出。

实现代码

class Solution {
public:vector<string> summaryRanges(vector<int>& nums) {vector<string> ret;int n = nums.size();int start, end;for (int i = 0; i < n;) {start = i;++i;while (i < n && nums[i] == nums[i-1] + 1) {++i;}end = i - 1;string tmp = to_string(nums[start]);if (start < end) {tmp += "->";tmp += to_string(nums[end]);}ret.push_back(tmp);}return ret;}
};

复杂度分析

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

空间复杂度：$O(1)$，只使用了有限个变量。

---

其他语言

python3

class Solution:def summaryRanges(self, nums: List[int]) -> List[str]:res = []i = 0n = len(nums)while i < n:    # i 是连续的左端点j = i       # j 是连续的右端点while j + 1 < n and nums[j+1] == nums[j] + 1:j += 1strs = str(nums[i]) if i == j else f'{nums[i]}->{nums[j]}'res.append(strs)i = j + 1return res

C

/*** Note: The returned array must be malloced, assume caller calls free().*/
char ** summaryRanges(int* nums, int numsSize, int* returnSize){char** res = malloc(sizeof(char*) * numsSize);*returnSize = 0;int i = 0;while (i < numsSize) {int low = i;++i;while (i < numsSize && nums[i] == nums[i-1] + 1) {++i;}int high = i - 1;char* tmp = malloc(sizeof(char) * 25);sprintf(tmp, "%d", nums[low]);if (low < high) {sprintf(tmp + strlen(tmp), "->");sprintf(tmp +strlen(tmp), "%d", nums[high]);}res[(*returnSize)++] = tmp;}return res;
}

sprintf 是一个 C 标准库函数，用于将格式化的数据写入字符串中，而不是标准输出流或文件。它的使用方式类似于 printf，但它不会将输出写入控制台，而是将其存储在指定的字符串中。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。