首页 > 代码库 > leetcode[163] Missing Ranges

leetcode[163] Missing Ranges


给定一个排好序的数组,和一个区间[lower, upper], 返回丢失的区间范围。例如:

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

在这里才发现c++版本的。

技术分享
string& makeRange(int lo, int hi){    static string result;    result="";    stringstream ss;    if (lo != hi){        ss << lo << "->" << hi;    }else{        ss << lo;    }    ss >> result;    return result;}vector<string> findMissingRanges(int A[], int n, int lower, int upper) {    vector<string> result;    if ( n<=0 ) {        result.push_back(makeRange(lower, upper));        return result;    }    if (lower < A[0]){        result.push_back(makeRange(lower, A[0]-1 < upper ? A[0]-1 : upper));    }    for(int i=0; i<n-1; i++){        if ( A[i] + 1 == A[i+1] ) {            continue;        }        result.push_back(makeRange(A[i]+1, A[i+1]-1));    }    if (upper > A[n-1]){        result.push_back(makeRange(A[n-1]+1, upper));    }    return result;}
View Code

就是先判断A[0]和lower的值,然后一个循环到n-1,一次输出符合要求的区间,最后还要判断A[n-1]和upper的值。

leetcode[163] Missing Ranges