C++ 中的包含重复 III
c++server side programmingprogramming更新于 2024/9/28 1:21:00
假设我们有一个整数数组，我们必须检查数组中是否有两个不同的索引 i 和 j，使得 nums[i] 和 nums[j] 之间的绝对差最多为 t。并且 i 和 j 之间的绝对差最多为 k。因此，如果输入为 [1,2,3,1]，则如果 k = 3 且 t = 0，则返回 true。
为了解决这个问题，我们将遵循以下步骤 −
创建一个集合 s, n := nums 数组的大小
for i in range 0 to n – 1
x 是从 nums[i] 开始的集合元素的索引
如果 x 不在集合范围内，并且 x 的值 <= nums[i] + t，则返回 true
如果 x 不是第一个元素
x := 下一个元素为随机
如果从 x 开始的第 t 个元素 >= nums[i]，则返回 true
将 nums[i] 插入 s，然后从 s 中删除 nums[i - k]
return false
示例(C++)
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
multiset <int> s;
int n = nums.size();
for(int i = 0; i< n; i++){
multiset <int> :: iterator x = s.lower_bound(nums[i]);
if(x != s.end() && *x <= nums[i] + t ) return true;
if(x != s.begin()){
x = std::next(x, -1);
if(*x + t >= nums[i])return true;
}
s.insert(nums[i]);
if(i >= k){
s.erase(nums[i - k]);
}
}
return false;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,1};
cout << (ob.containsNearbyAlmostDuplicate(v, 3,0));
}
输入
[1,2,3,1] 3 0
输出
1
