C++ 中的缺失值范围
c++server side programmingprogramming
假设我们有一个已排序的整数数组 nums，其元素范围在 [lower, upper] 包含的范围内，我们需要找到缺失值的范围。
因此，如果输入为 nums = [0, 1, 3, 50, 75]，其中 lower 值为 0，upper 值为 99，则输出为 ["2","4->49","51->74","76->99"]
为了解决这个问题，我们将遵循以下步骤 −
定义一个数组 nums
定义一个集合 v
初始化 i := 0，当 i < t 的大小时，更新(将 i 加 1)，执行 −
如果 t[i] 不在 v 中，则 −
将 t[i] 插入到 v 中
将 t[i] 插入到 nums 的末尾
定义一个名为 ret 的数组
curr := lower
i := 0, n := nums 的大小
当 curr <= upper 时，执行 −
如果 i < n 且 nums[i] 与 curr 相同，则 −
(将 i 加 1)
(将 curr 加 1)
否则
temp := 将 curr 转换为字符串
(将 curr 加 1)
如果 i < n 且 nums[i] 与 curr 相同，则 −
在 ret 末尾插入 temp
忽略以下部分，跳至下一次迭代
否则
如果 i 与 n 相同，则 −
如果 curr <= upper，则 −
temp := "->"
temp := temp 将 upper 连接为字符串
curr := upper + 1
在 ret 末尾插入 temp
否则
temp := "->"
curr := nums[i]
temp := temp 将 (curr - 1) 连接为字符串
curr := nums[i]
在 ret 末尾插入 temp
return ret
示例
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string< findMissingRanges(vector<int<& t, int lower, int upper) {
vector <int< nums;
set <long long int> v;
for(int i = 0; i < t.size(); i++){
if(!v.count(t[i])){
v.insert(t[i]);
nums.push_back(t[i]);
}
}
vector < string > ret;
long long int curr = lower;
int i = 0;
int n = nums.size();
while(curr <= upper){
if(i < n && nums[i] == curr){
i++;
curr++;
}
else{
string temp = to_string(curr);
curr++;
if(i < n && nums[i] == curr){
ret.push_back(temp);
continue;
}
else{
if(i == n){
if(curr <= upper){
temp += "->";
temp += to_string(upper);
curr = (long long int )upper + 1;
}
ret.push_back(temp);
}
else{
temp += "->";
curr = nums[i];
temp += to_string(curr - 1);
curr = nums[i];
ret.push_back(temp);
}
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<int< v = {0,1,3,50,75};
print_vector(ob.findMissingRanges(v, 0, 99));
}
输入
{0,1,3,50,75}, 0, 99
输出
[2, 4->49, 51->74, 76->99, ]
