如何把网站上传到空间,wordpress快站,信息发布,大城怎么样做网站文章目录 Tag题目来源题目解读解题思路方法一#xff1a;一次遍历复杂度分析 其他语言python3C 写在最后 Tag
【一次遍历】【数组】【字符串】 题目来源
228. 汇总区间 题目解读
给定一个无重复的升序数组 nums#xff0c;需要将这个数组按照以下规则进行汇总#xff1… 文章目录 Tag题目来源题目解读解题思路方法一一次遍历复杂度分析 其他语言python3C 写在最后 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:vectorstring summaryRanges(vectorint nums) {vectorstring 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 ) O(n) O(n) n n n 为数组 num 的长度。
空间复杂度 O ( 1 ) O(1) 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[j1] nums[j] 1:j 1strs str(nums[i]) if i j else f{nums[i]}-{nums[j]}res.append(strs)i j 1return resC
/*** 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但它不会将输出写入控制台而是将其存储在指定的字符串中。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
