資料結構
網路
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 次瀏覽
廣告