โจทย์
กำหนดอาร์เรย์จำนวนเต็ม ตรวจสอบว่ามีดัชนี i และ j ที่ต่างกันทำให้:
|nums[i] - nums[j]| <= t(ความต่างค่าสัมบูรณ์ ≤ t)|i - j| <= k(ความต่างดัชนีสัมบูรณ์ ≤ k)
ตัวอย่าง: nums = [1,2,3,1], k = 3, t = 0 → คืน true เพราะ nums[0] และ nums[3] เท่ากันและห่างกัน 3 ดัชนี
แนวคิด: Sliding Window + Ordered Set (multiset)
รักษาช่วงเลื่อนขนาด k ด้วย multiset เพื่อค้นหาค่าที่ใกล้เคียงได้ใน O(log k)
ขั้นตอน
- สร้าง
multiset<int> s - ลูป
i = 0 ถึง n-1:- หา
x = s.lower_bound(nums[i])(ค่าแรก ≥ nums[i]) - ถ้า
x != s.end() && *x <= nums[i] + t→ คืน true - ถ้า
x != s.begin()→ ตรวจค่าก่อนหน้าprev(x)ว่า*prev(x) + t >= nums[i] - เพิ่ม
nums[i]ลง set - ถ้า
i >= k→ ลบ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<long long> s; // ใช้ long long ป้องกัน overflow
int n = nums.size();
for (int i = 0; i < n; i++) {
auto x = s.lower_bound((long long)nums[i]);
if (x != s.end() && *x - nums[i] <= t) return true;
if (x != s.begin()) {
auto prev_x = prev(x);
if (nums[i] - *prev_x <= t) return true;
}
s.insert(nums[i]);
if (i >= k) s.erase(s.find(nums[i - k]));
}
return false;
}
};
int main() {
Solution ob;
vector<int> v = {1,2,3,1};
cout << ob.containsNearbyAlmostDuplicate(v, 3, 0); // 1 (true)
return 0;
}อินพุต / เอาต์พุต
Input: [1,2,3,1] 3 0
Output: 1 (true)
ความซับซ้อน
- Time: O(n log k) - แต่ละรอบ insert/erase/lower_bound ใช้ log k
- Space: O(k) - เก็บได้สูงสุด k องค์ประกอบ
