Schreiben Sie ein Programm in C++, um den k-kleinsten Unterschied zwischen allen Elementpaaren in einem Array zu ermitteln

Angenommen, wir haben eine Liste mit mehreren ganzen Zahlen. Wir müssen die Differenz zwischen jedem Wertepaar im Array ermitteln und die k-te kleinste Anzahl an Differenzen ermitteln. Der Index beginnt bei 0 und der Wert k wird uns als Eingabe übergeben.

Wenn die Eingabe also etwa Zahlen = {2, 6, 4, 8}, k = 2 ist, dann ist die Ausgabe 2.

Der Unterschied zwischen den beiden Paaren beträgt -

(2, 6) = 4

(2, 4) = 2

(2, 8) = 6

(6, 4) = 2

(6 , 8) = 2

(4, 8) = 4

Wenn wir diese Werte sortieren, wird daraus 2, 2, 2, 4, 4, 6. Der zweite Mindestwert ist 2. (indiziert von 0).

Um dieses Problem zu lösen, werden wir die folgenden Schritte ausführen:

• k um 1 erhöhen
• Array-Eingabe sortieren
• le := 0
• ri := Letztes Element der Eingabe – Erstes Element der Eingabe
• while le
• mid := (le + ri) / 2
• tmp := 0
• lp := 0
• wird verwendet, um i := 1 zu initialisieren, wenn i
• while input[i] - input[lp] > mid,execute −
  • lp := lp + 1
• tmp := tmp + i - lp

if tmp >= k, then -

• ri := mid

Ansonsten

• le := mid + 1

return le

Beispiel

Schauen wir uns die folgende Implementierung an, um die Eingabe besser zu verstehen

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

Ausgabe

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

Das obige ist der detaillierte Inhalt vonSchreiben Sie ein Programm in C++, um den k-kleinsten Unterschied zwischen allen Elementpaaren in einem Array zu ermitteln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!