Given a sorted integer array without duplicates, return the summary of its ranges.
Example 1:
Input: [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.
Example 2:
Input: [0,2,3,4,6,8,9] Output: ["0","2->4","6","8->9"] Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.
给定一个数组，把数组汇总成若干个连续的区间，以字符串的形式给出。
方法是判断两个相邻的数之差是否为1，不是1则前面的构成一个区间，转换为字符串输出。判断前一个区间只有一个数还是有多个数的方法是区间的起止位置i,j是否相差1，如果是，则只有一个数，否则有多个数。
注意最后一个区间需要在while循环外部判断。代码如下：
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums)
{
vector<string> ans;
int n = nums.size(), i = 0, j = 1;
if (n == 0)
return ans;
while (j < n) {
if (nums[j] – nums[j – 1] == 1)
++j;
else {
if (j – i == 1)
ans.push_back(to_string(nums[i]));
else
ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j – 1]));
i = j++;
}
}
if (j – i == 1)
ans.push_back(to_string(nums[i]));
else
ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j – 1]));
return ans;
}
};本代码提交AC，用时0MS。
还有一种解法利用了二分查找的思路，很有意思，参考讨论区。
假如给定的数组是[1,2,3,4,5,…,10000,20000]，如果还是用上述方法，时间复杂度是O(n)，至少需要遍历一遍数组。但是数组的前10000个数是严格有序且连续递增的，如果能把这一部分识别出来，直接转换为”1->10000″，则速度会大大提高。
二分查找的思路是，对于给定区间[a,…,b]，假设其在数组中的下标起点分别为[i,…,j]，则如果b-a==j-i，说明[a,b]之间是类似上面的[1,2,…,10000]的情况的，因为数组中没有重复元素，所以区间有j-i个元素，且元素最大值和最小值的差b-a也是j-i，说明他们是一个连续的有序区间，我们直接把这个区间转换为”a->b”。
否则如果j-i!=b-a，则取中点mid=(i+j)/2，递归在[i,mid]和[mid+1,j]进行。
有一种情况需要注意的是，分割出来的区间可能需要合并，比如[1,2,3,4,5,6,8]，初始i[1,..,8]不满足b-a==j-i，所以递归在[1,2,3,4]和[5,6,8]进行。左边转换为了”1->4″，右边还需要递归，假设转换为了”5->6″和”8″，那么”1->4″和”5->6″是需要合并的。所以我们在插入”5->6″时，看看之前得到的区间”1->4″的end是否和当前区间”5->6″的start只差1，如果是，则需要合并，更新之前区间的end为现在要插入区间的end，变成了”1->6″。
完整代码如下：
class Solution {
private:
struct Range {
int start, end;
Range(int s, int e)
: start(s)
, end(e){};
};
void add2Ans(int a, int b, vector<Range>& ranges)
{
if (ranges.empty() || ranges[ranges.size() – 1].end != a – 1) {
ranges.push_back(Range(a, b));
}
else {
ranges[ranges.size() – 1].end = b;
}
}
void helper(vector<int>& nums, int start, int end, vector<Range>& ranges)
{
if (start == end || end – start == nums[end] – nums[start]) {
add2Ans(nums[start], nums[end], ranges);
return;
}
int mid = start + (end – start) / 2;
helper(nums, start, mid, ranges); // 先左区间
helper(nums, mid + 1, end, ranges); // 后右区间
}
public:
vector<string> summaryRanges(vector<int>& nums)
{
vector<string> ans;
if (nums.empty())
return ans;
vector<Range> ranges;
helper(nums, 0, nums.size() – 1, ranges);
for (const auto& r : ranges) {
if (r.start == r.end)
ans.push_back(to_string(r.start));
else
ans.push_back(to_string(r.start) + "->" + to_string(r.end));
}
return ans;
}
};本代码提交AC，用时0MS。
这个代码在数据有很多连续区间时，接近O(lgn)的复杂度。但是当数据全是不连续的时，比如[1,3,5,7,9]，则只有到递归到最深层start==end（即针对单个数字）时，才得到一个区间，所以退化为O(n)的算法。
如果再follow up可能有重复元素时，上述二分查找的方法就不管用了，因为属于一个区间的不一定满足b-a==j-i，比如[1,2,2,2,3]，b-a=2，而j-i=4。此时只能用第一种O(n)的方法：
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums)
{
vector<string> ans;
if (nums.empty())
return ans;
int i = 0, j = 1, n = nums.size();
while (j < n) {
while (j < n && (nums[j] == nums[j – 1] || nums[j] – nums[j – 1] == 1))
++j; // 考虑重复元素
if (j >= n)
break;
if (j – 1 == i)
ans.push_back(to_string(nums[i]));
else
ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j – 1]));
i = j++;
}
if (j – 1 == i)
ans.push_back(to_string(nums[i]));
else
ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j – 1]));
return ans;
}
};本代码提交AC，用时0MS。
二刷。更加鲁邦容易理解的代码：
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<vector<int>> ranges;
int i = 0, n = nums.size();
while (i < n) {
int j = i + 1;
while (j < n&&nums[j] == nums[j - 1] + 1)++j;
ranges.push_back({ nums[i],nums[j - 1] });
i = j;
}
vector<string> ans;
for (int i = 0; i < ranges.size(); ++i) {
if (ranges[i][0] == ranges[i][1]) {
ans.push_back(to_string(ranges[i][0]));
}
else {
ans.push_back(to_string(ranges[i][0]) + "->" + to_string(ranges[i][1]));
}
}
return ans;
}
};本代码提交AC，用时0MS。