แนวคิด
สมมติว่ามีอาร์เรย์และจำนวนเต็ม k ให้ตรวจสอบว่ามีดัชนี i และ j ที่แตกต่างกันในอาร์เรย์ที่ทำให้ nums[i] = nums[j] และความต่างสัมบูรณ์ระหว่าง i และ j น้อยกว่าหรือเท่ากับ k หรือไม่
เช่น ถ้าอินพุตคือ [1,2,4,1] และ k = 3 ผลลัพธ์คือ True
วิธีแก้:
- กำหนดอาร์เรย์ nn ของคู่
- วนลูป i := 0 ถึงขนาด nums - 1: แทรก {nums[i], i} ลงท้าย nn
- เรียงอาร์เรย์ nn
- วนลูป i := 1 ถึงขนาด nn - 1: ถ้าองค์ประกอบแรกของ nn[i] เท่ากับองค์ประกอบแรกของ nn[i-1] และ |second of nn[i] - second of nn[i-1]|: คืนค่า true
- คืนค่า false
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
vector<pair<int, int>> nn;
for (int i = 0; i < nums.size(); i++) {
nn.push_back(make_pair(nums[i], i));
}
sort(nn.begin(), nn.end());
for (int i = 1; i < nn.size(); i++) {
if (nn[i].first == nn[i - 1].first and abs(nn[i].second - nn[i - 1].second) <= k)
return true;
}
return false;
}
};
main() {
Solution ob;
vector<int> v = {1,2,4,1};
cout << (ob.containsNearbyDuplicate(v, 3));
}
อินพุต
{1,2,4,1}
เอาต์พุต
1
