数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中包含 Duplicate III
假设我们有一个整数数组，我们需要检查数组中是否存在两个不同的索引 i 和 j，使得 nums[i] 和 nums[j] 之间的绝对差值至多为 t。而 i 和 j 之间的绝对差值至多为 k。因此，如果输入为 [1,2,3,1]，则如果 k = 3 且 t = 0，则返回 true。
要解决这个问题，我们将遵循以下步骤 −
生成一个集合 s，n := nums 数组的长度
对于 i，范围为 0 至 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]
返回 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
更新日期：02-5 月-2020 年
266 次浏览
广告