首页 > 代码库 > 【LeetCode】Missing Ranges
【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"].
逐个数组元素遍历,将间隙取出即可。注意两边的情况。
class Solution {public: vector<string> findMissingRanges(int A[], int n, int lower, int upper) { vector<string> ret; if(n == 0) return ret; string str; if(lower < A[0]) { if(lower < A[0]-1) str = to_string((long long)lower) + "->" + to_string((long long)A[0]-1); else //lower == A[0]-1 str = to_string((long long)lower); ret.push_back(str); } for(int i = 1; i < n; i ++) { if(A[i] - A[i-1] < 2) continue; if(A[i] - A[i-1] > 2) str = to_string((long long)A[i-1]+1) + "->" + to_string((long long)A[i]-1); else //A[i] - A[i-1] == 2 str = to_string((long long)A[i-1]+1); ret.push_back(str); } if(A[n-1] < upper) { if(A[n-1] < upper-1) str = to_string((long long)A[n-1]+1) + "->" + to_string((long long)upper); else //upper == A[n-1]+1 str = to_string((long long)upper); ret.push_back(str); } return ret; }};
以下是我的测试用例,全部通过:
void display(vector<string>& ret){ for(int i = 0; i < ret.size(); i ++) { cout << ret[i] << " "; } cout << endl;}int main(){ Solution s; int A[1]; //expect: ["0->9"] vector<string> ret = s.findMissingRanges(A, 0, 0, 9); display(ret); int B[1] = {6}; //expect: ["0->5", "7->9"] ret = s.findMissingRanges(B, 1, 0, 9); display(ret); int C[3] = {0, 1, 2}; //expect: [] ret = s.findMissingRanges(C, 3, 0, 2); display(ret); int D[5] = {0, 1, 3, 50, 75}; //expect: ["2", "4->49", "51->74", "76->99"] ret = s.findMissingRanges(D, 5, 0, 99); display(ret);}
【LeetCode】Missing Ranges
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。