सी++ में एक सरणी में सभी तत्व जोड़े के बीच के-वें सबसे छोटे अंतर का पता लगाने का कार्यक्रम

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

इसलिए, यदि इनपुट संख्या ={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 है। (सूचकांक 0 से शुरू होता है)।

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

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

वापसी ले

उदाहरण

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

#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;