C++ में सरणी में सभी तत्व युग्मों के बीच k-वां सबसे छोटा अंतर ज्ञात करने का प्रोग्राम

मान लीजिए हमें कई पूर्णांक संख्याओं वाली एक सूची दी गई है। हमें सरणी में मानों के प्रत्येक युग्म के बीच का अंतर ढूंढना है और k-वां सबसे छोटा अंतर नंबर ढूंढना है। सूचकांक 0 से शुरू होता है और मान k हमें इनपुट के रूप में दिया जाता है।

तो, यदि इनपुट numbers = {2, 6, 4, 8}, k = 2 है, तो आउटपुट 2 होगा।

युग्मों के बीच अंतर हैं:

(2, 6) = 4

(2, 4) = 2

(2, 8) = 6

(6, 4) = 2

(6, 8) = 2

(4, 8) = 4

यदि हम मानों को क्रमबद्ध करते हैं, तो यह 2, 2, 2, 4, 4, 6 बन जाता है। 2-रा सबसे छोटा मान 2 है। (सूचकांक 0 से शुरू होता है)।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

k को 1 से बढ़ाएं
इनपुट सरणी को क्रमबद्ध करें
le := 0
ri := इनपुट का अंतिम तत्व - इनपुट का पहला आइटम
जब le < ri, करें:
- mid := (le + ri) / 2
- tmp := 0
- lp := 0
- i := 1 से प्रारंभ करें, जब i < इनपुट का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
  - जब input[i] - input[lp] > mid, करें:
    - lp := lp + 1
  - tmp := tmp + i - lp
- यदि tmp >= k, तो:
  - ri := mid
- अन्यथा:
  - le := mid + 1
le लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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

int solve(vector<int>& input, int k) {
    k++;
    sort(input.begin(), input.end());
    int le = 0;
    int ri = input.back() - input[0];
    while (le < ri) {
        int mid = (le + ri) / 2;
        long long tmp = 0;
        int lp = 0;
        for (int i = 1; i < input.size(); i++) {
            while (input[i] - input[lp] > mid) lp++;
            tmp += i - lp;
        }
        if (tmp >= k) ri = mid;
        else le = mid + 1;
    }
    return le;
}

int main() {
    vector<int> numbers = {2, 6, 4, 8};
    cout << solve(numbers, 2) << endl;
    return 0;
}

इनपुट

vector<int> numbers = {2, 6, 4, 8};
cout << solve(numbers, 2) << endl;