链接
https://leetcode-cn.com/problems/summary-ranges/
耗时
解题:12 min
题解:9 min
题意
给定一个无重复元素的有序整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出:
- “a->b” ,如果 a != b
- “a” ,如果 a == b
思路
遍历一趟,如果当前数字加一等于下一个数字,则区间右端点值加一,不等则加入结果。如果区间左右端点值相等,则加入当前元素,否则加入这个区间;并置新区间的左右端点的值为下一个数字的位置。
时间复杂度:
O
(
n
)
O(n)
O(n)
AC代码
class Solution {
public:
string Int_to_String(int x) {
ostringstream ss;
ss<<x;
return ss.str();
}
vector<string> summaryRanges(vector<int>& nums) {
int n = nums.size();
int l = 0, r = 0;
vector<string> ans;
for(int i = 0; i < n; ++i) {
if(i != n-1 && nums[i]+1 == nums[i+1]) {
r++;
}
else {
if(l == r) {
ans.push_back(Int_to_String(nums[l]));
}
else {
ans.push_back(Int_to_String(nums[l])+"->"+Int_to_String(nums[r]));
}
l = r = i+1;
}
}
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)