Given a sorted integer array where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
For example, given
[0, 1, 3, 50, 75]
, lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
[Thoughts]
这题并不难,扫一遍数组,对于任意两个相邻的数字,看看他们是否连续,不连续的话生成一个range。
需要注意两点:
1. 可以把lower和upper两个边界值加入到数组里面去,这样避免不必要的if-else。 因为lower和upper不是数组中的数字,他们可以出现在range里面,所以这里添加的边界应该是lower -1 和upper +1
2. 测试数据中有很多边界检测,可以直接用int64_t来跳过检测,省了繁琐的if-else
[Code]
1: vector<string> findMissingRanges(vector<int>& ori_nums, int lower, int upper) {
2: int64_t right = upper;
3: int64_t left = lower;
4: if(ori_nums.size() == 0) return {getRange(left-1, right+1)};
5: vector<int64_t> nums(ori_nums.size());
6: std::copy ( ori_nums.begin(), ori_nums.end(), nums.begin() );
7:
8: // insert lower and upper as boundary of the array
9: nums.insert(nums.begin(), left-1);
10: nums.push_back(right+1);
11:
12: int64_t pre = nums[0];
13: vector<string> result;
14: for(int i = 1; i< nums.size(); i++) {
15: if(nums[i]- pre > 1) {
16: string range = getRange(pre, nums[i]);
17: result.push_back(range);
18: }
19: pre = nums[i];
20: }
21: return result;
22: }
23:
24: string getRange(int64_t start, int64_t end) {
25:
26: if(end - start <= 2) return to_string(start+1);
27:
28: return to_string(start+1) + "->" + to_string(end-1);
29: }
No comments:
Post a Comment