สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม เราต้องตรวจสอบว่ามีดัชนี i และ j ที่แตกต่างกันสองตัวในอาร์เรย์หรือไม่ โดยที่ความแตกต่างที่แน่นอนระหว่าง nums[i] และ nums[j] ไม่เกิน t และความแตกต่างที่แน่นอนระหว่าง i กับ j อยู่ที่ k มากที่สุด ดังนั้นหากอินพุตเป็นเช่น [1,2,3,1] ถ้า k =3 และ t =0 ให้คืนค่า จริง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างชุด s, n :=ขนาดของอาร์เรย์ nums
-
สำหรับฉันอยู่ในช่วง 0 ถึง n – 1
-
x คือดัชนีขององค์ประกอบชุดที่เริ่มต้นจาก nums[i] ขึ้นไป
-
ถ้า x ไม่อยู่ในช่วงของชุดและค่าของ x <=nums[i] + t แล้วคืนค่า true
-
ถ้า x ไม่ใช่องค์ประกอบแรก
-
x :=องค์ประกอบถัดไปแบบสุ่ม
-
ถ้าองค์ประกอบที่ t เริ่มต้นจาก x คือ>=nums[i] แล้วคืนค่า true
-
-
ใส่ nums[i] ลงใน s แล้วลบ nums[i - k] ออกจาก s
-
-
คืนค่าเท็จ
ตัวอย่าง(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
