समस्या विवरण
मान लीजिए हमारे पास एक सरणी और एक पूर्णांक k है, हमें जांचना है कि क्या सरणी में दो अलग-अलग इंडेक्स i और j हैं जैसे कि nums[i] = nums[j] और i और j के बीच का निरपेक्ष अंतर अधिकतम k है।
उदाहरण
यदि इनपुट है: [1,2,4,1] और k = 3, तो आउटपुट होगा True
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें:
- जोड़े की एक सरणी nn परिभाषित करें
- i := 0 से आरंभ करें, जब i < nums का आकार, i को 1 से बढ़ाते हुए:
- {nums[i], i} को nn के अंत में डालें
- सरणी nn को सॉर्ट करें
- i := 1 से आरंभ करें, जब i < nn का आकार, i को 1 से बढ़ाते हुए:
- यदि nn[i] का पहला तत्व, nn[i-1] के पहले तत्व के समान है और |nn[i] का दूसरा - nn[i-1] का दूसरा| <= k:
- true लौटाएं
- यदि nn[i] का पहला तत्व, nn[i-1] के पहले तत्व के समान है और |nn[i] का दूसरा - nn[i-1] का दूसरा| <= k:
- false लौटाएं
C++ कार्यान्वयन
#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 && abs(nn[i].second - nn[i - 1].second) <= k)
return true;
}
return false;
}
};
int main() {
Solution ob;
vector<int> v = {1,2,4,1};
cout << (ob.containsNearbyDuplicate(v, 3));
return 0;
}
इनपुट
{1,2,4,1}
आउटपुट
1