[leetcode] Missing Ranges


Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, 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"].

check stores the current number we want to check in the nums.

if check appears in the nums, check++, go to next loop

else, test if it is a single word or a range covers several words.

push_back upper + 1 in to the nums array would dramatically simplify the structure in our program.

class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> ans;
        string str;
        int check = lower;
        nums.push_back(upper + 1);//overflow?
        for(int num: nums){
            if(check == num){
                //continues
                check++;
            }
            else{
                //not continues
                int end = num - 1;
                if(end == check){
                    //single number missing
                    str.clear();
                    str.append(to_string(check));
                    ans.push_back(str);
                }
                else{
                    //a range of numbers missing
                    str.clear();
                    str.append(to_string(check));
                    str.append("->");
                    str.append(to_string(end));
                    ans.push_back(str);
                }
                check = num + 1;
            }
        }
        return ans;
    }
};

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.