LeetCode Summary Ranges

LeetCode Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].


给定一个数组,把数组汇总成若干个连续的区间,以字符串的形式给出。

方法是判断两个相邻的数之差是否为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。

Leave a Reply

Your email address will not be published. Required fields are marked *