Google+ Followers

Saturday, July 22, 2017

[Leetcode] Missing Ranges, Solution

Given a sorted integer array where the range of elements are in the inclusive range [lowerupper], 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:    }  
Post a Comment