Thursday, April 9, 2015

LeetCode [163] Missing Ranges

163. Missing Ranges
Medium
Given a sorted integer array nums, where the range of elements are in the inclusive range [lowerupper], return its missing ranges.
Example:
Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]
========
* keep update lower bound "l"
* use "long long" to resolve overflow
========

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef long long ll;
class Solution {
public:
    void updateIntv(ll l, ll r, vector<string>& ret)
    {
        if(l==r) ret.push_back(to_string(l));
        if(l<r) ret.push_back(to_string(l)+"->"+to_string(r));
    }
    
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> ret;
        int n = nums.size(), i = 0;
        ll l = lower;
        while(i<n){
            ll v = nums[i++];
            updateIntv(l, v-1, ret);
            l = v+1;
        }
        updateIntv(l, upper, ret);
        return ret;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> list = new ArrayList<>();
        int left = lower;
        for(int i : nums){
            int right = i-1;
            if(right>left){
                list.add(left + "->" + right);
            }else if(right==left){
                list.add(String.valueOf(left));
            }
            left = i+1;
        }
        
        if(left<=upper){
            if(left==upper) list.add(String.valueOf(left));
            else list.add(left + "->" + upper);
        }
        
        return list;
    }
}

No comments:

Post a Comment