C++ में सरणी में K-डिफ जोड़े

समस्या विवरण

मान लीजिए हमारे पास एक सरणी और एक पूर्णांक k है, हमें सरणी में अद्वितीय k-डिफ जोड़े की संख्या ज्ञात करनी है। यहां k-डिफ जोड़ा (i, j) जैसा होता है, जहां i और j दोनों सरणी में मौजूद हैं और उनका निरपेक्ष अंतर k है।

उदाहरण

यदि इनपुट है: [3,1,4,1,5], k = 2, तो आउटपुट होगा 2, क्योंकि सरणी में दो 2-डिफ जोड़े हैं: (1,3) और (3,5)।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें:

• seen और done नामक मैप परिभाषित करें
• एक सेट s परिभाषित करें
• यदि k < 0, तो 0 लौटाएं
• i := 0 से आरंभ करें, जब i < nums का आकार, i को 1 से बढ़ाते हुए:
  • seen[nums[i]] को 1 से बढ़ाएं
  • nums[i] को s में डालें
• ans := 0
• s में प्रत्येक तत्व it के लिए:
  • यदि k, 0 के बराबर है:
    • यदि seen[it] > 1, तो ans को 1 से बढ़ाएं
  • अन्यथा:
    • done[it] को 1 से बढ़ाएं
    • यदि (it + k) seen में है लेकिन done में नहीं, तो ans को 1 से बढ़ाएं
    • यदि (it - k) seen में है लेकिन done में नहीं, तो ans को 1 से बढ़ाएं
• ans लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        map<int, int> seen, done;
        set<int> s;
        if (k < 0)
            return 0;
        for (int i = 0; i < nums.size(); i++) {
            seen[nums[i]]++;
            s.insert(nums[i]);
        }
        int ans = 0;
        for (auto it = s.begin(); it != s.end(); it++) {
            if (k == 0) {
                if (seen[*it] > 1)
                    ans++;
            } else {
                done[*it]++;
                if (seen.find(*it + k) != seen.end() && done.find(*it + k) == done.end())
                    ans++;
                if (seen.find(*it - k) != seen.end() && done.find(*it - k) == done.end())
                    ans++;
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,1,4,1,5};
    cout << (ob.findPairs(v, 2));
    return 0;
}

इनपुट

{3,1,4,1,5}, 2

आउटपुट

2