Mind palace

some thoughts

0%

163. Missing Ranges

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> res;
        nums.push_back(upper); // padding好处理，而且nums可能是空的
        long l = lower;
        for (auto it = lower_bound(begin(nums), end(nums), lower);
            it != upper_bound(begin(nums), end(nums), upper);
            ++it) {
            long u = it == prev(end(nums)) ? *it : *it - 1L; // 注意integer overflow，比如[-2147483648, 0]
            if (l == u) {
                res.push_back(to_string(l));
            } else if (l < u) {
                res.push_back(to_string(l) + "->" + to_string(u));
            }
            l = *it + 1L;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        int n = size(nums);
        vector<string> res;
        nums.push_back(upper); // padding好处理，而且nums可能是空的
        long l = lower;
        for (int i = 0; i <= n; ++i) {
            long u = i == n ? nums[i] : ((long)nums[i] - 1); // 注意integer overflow，比如[-2147483648, 0]
            if (l == u) {
                res.push_back(to_string(l));
            } else if (l < u) {
                res.push_back(to_string(l) + "->" + to_string(u));
            }
            l = (long)nums[i] + 1;
        }
        return res;
    }
};

O(n) time O(n) space
先按照228. Summary Ranges总结现有区间，然后再找出missing区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<pair<long, long>> v;
        v.emplace_back(LONG_MIN, lower - 1L);
        vector<string> res;
        auto add = [&v](long x) {
            if (v.back().second + 1 < x) {
                v.emplace_back(x, x);
            } else {
                v.back().second = x;
            }
        };
        for (auto it = lower_bound(begin(nums), end(nums), lower);
            it != upper_bound(begin(nums), end(nums), upper);
            ++it) {
            add(*it);
        }
        add(upper + 1L);
        for (int i = 1; i < size(v); ++i) {
            if (v[i - 1].second + 2 < v[i].first) {
                res.push_back(to_string(v[i - 1].second + 1) + "->" + to_string(v[i].first - 1));
            } else {
                res.push_back(to_string(v[i].first - 1));
            }
        }
        return res;
    }
};