Share my c++ sol (binary search)


  • 0
    M

    I used binary to search for the first element A[i] that satisfies A[i] >= lower (like the std::lower_bound()). By definition, A[i-1] < lower and we can thus totally forget about anything from 0~i-1. Note that we will need to push back the range [lower,A[i]-1] if A[i] > lower.

    Then again use binary search to search for the first element A[j] that satisfies A[j] >= upper. So we will have A[j-1] < upper. (Note that the lower_bound function works in such a way the if the last/largest element A[n-1] is less than upper than it outputs n-1. So you will need to check if it is j or j-1 that should be used as a upper bound in the following linear finding missing ranges)

    Now we know that

    lower <= A[i] <= A[j-1] (or A[j]) <= upper

    so we can do linear search for missing ranges in this block.

    vector<string> findMissingRanges(int A[], int n, int lower, int upper) {
        vector<string> result;
        if(n==0 || lower > A[n-1] || upper < A[0]) 
            return {getRange(lower,upper)};
        
        int start = lower_bound(A,0,n-1,lower);
        if(lower < A[start]) result.push_back(getRange(lower,A[start]-1));
        int end = lower_bound(A,start,n-1,upper);
        if(upper <= A[end]) end--;
        for(int i=start; i<end; i++) {
            if(i+1>end) break;
            if(A[i+1]-A[i]>1) result.push_back(getRange(A[i]+1,A[i+1]-1)); 
        }
        if(upper > A[end]) result.push_back(getRange(A[end]+1,upper));
        return result;
    }
    

    The helper functions:

    string getRange(int i, int j) {
        if(i==j) return to_string(i);
        else return to_string(i) + "->" + to_string(j);
    }
    int lower_bound(int A[], int i, int j, int target) {
        while(i < j) {
            int m = i+(j-i)/2;
            if(target > A[m]) i=m+1;
            else j=m;
        }
        return j;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.