【面试经典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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析

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

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

---

其他语言

python3

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        res = []
        i = 0
        n = len(nums)
        
        while i < n:    # i 是连续的左端点
            j = i       # j 是连续的右端点
            while j + 1 < n and nums[j+1] == nums[j] + 1:
                j += 1
            strs = str(nums[i]) if i == j else f'{nums[i]}->{nums[j]}'
            res.append(strs)
            i = j + 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

---

写在最后

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

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

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