Summary Ranges

228. Summary Range

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"].

S: loop O(n)

vector<string> summaryRanges(vector<int>& nums) {
  vector<string> result;
  int i = 0;
  while(i < nums.size()){
      string range = to_string(nums[i]);
      int j = i+1;
      while(j < nums.size() && nums[j] == nums[j-1]+1) j++;
      if(j-1 > i) range += "->" + to_string(nums[j-1]);
      result.push_back(range);
      i = j;
  }
  return result;
}

1. Missing Ranges [Locked] Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges. For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]

S: simple iteraton

循环地先搜索missing range的起点，从当前已覆盖位置last（初始为-1)开始，每次检查nums[k]<=last+1，如果是则更新last=nums[k]，否则设置start为已覆盖位置+1。最后一个数为nums[k+1]-1，或99.

vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    int last = lower-1;
    vector<string> result;
    for (int v : nums) {
        if (v > last+1) result.push_back(rangeStr(last+1, v-1));
        last = v;
    }
    if (last < upper) result.push_back(rangeStr(last+1, upper));
}


inline string rangeStr(int left, int right) {
    string ret = to_string(left);
    if (right > left) ret += "->" + to_string(right);
    return ret;
}

163. Missing Ranges

Given a sorted integer array wherethe range of elements are in the inclusive range [lower,upper], return its missing ranges.

For example, given[0, 1, 3, 50, 75],lower= 0 andupper= 99, return["2", "4->49", "51->74", "76->99"].

S：loop O(n)

注意开头结尾的处理，空数组处理和溢出处理

class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        int begin = lower;
        vector<string> result;
        int n = nums.size();
        if (n == 0) {
            string s = lower == upper? to_string(lower) : to_string(lower) + "->" + to_string(upper);
            result.push_back(s);
            return result;
        }
        for (int i = 0; i < n; ++i) {              
            if (nums[i] > INT_MIN && begin == nums[i] - 1) {
                result.push_back(to_string(begin));
            } else if (nums[i] > INT_MIN && begin < nums[i] - 1) {
                string s = to_string(begin) + "->" + to_string(nums[i] - 1);
                result.push_back(s);
            }    
            if (nums[i] == INT_MAX) break;
            begin = nums[i] + 1;
        }
        if (nums[n - 1] == upper - 1) {
            result.push_back(to_string(upper));
        } else if (nums[n - 1] < upper) {
            string s = to_string(nums[n - 1] + 1) + "->" + to_string(upper);
            result.push_back(s);
        }
        return result;
    }
};