博文中会简要介绍Leetcode P0163题目分析及解题思路。
“Missing Ranges”是一道比较简单的题目。由于给定的数组已经排好序了，我们只需要遍历一边数组即可。我们维护两个量，分别表示所求的区间的左边界和右边界，然后根据数组中的元素更新左右边界。
You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.
A number x is considered missing if x is in the range [lower, upper] and x is not in nums.
Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.
Each range [a,b] in the list should be output as:
- “a->b” if a != b
- “a” if a == b
以下是Java的题解代码实现。
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
int N = nums.length;
List<String> missingRanges = new ArrayList<>();
int left = lower, right = lower-1;
for (int idx=0; idx<N; ++idx) {
right = nums[idx]-1;
if (right >= left) {
missingRanges.add((left < right)? left+"->"+right: String.valueOf(left));
}
left = nums[idx]+1;
}
if (left <= upper) {
missingRanges.add((left < upper)? left+"->"+upper: String.valueOf(left));
}
return missingRanges;
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
int N = nums.size();
vector<string> missing;
int left = lower, right = lower-1;
for (int idx=0; idx<N; ++idx) {
right = nums[idx]-1;
if (right >= left) {
string left_str = to_string(left);
missing.push_back((left < right)? left_str+"->"+to_string(right): left_str);
}
left = nums[idx]+1;
}
if (left <= upper) {
string left_str = to_string(left);
missing.push_back((left < upper)? left_str+"->"+to_string(upper): left_str);
}
return missing;
}
};