Écrivez un programme en C++ pour trouver la kième plus petite différence entre toutes les paires d'éléments d'un tableau

Supposons que nous ayons une liste contenant plusieurs nombres entiers. Nous devons trouver la différence entre chaque paire de valeurs du tableau et trouver le kième plus petit nombre de différences. L'index part de 0 et la valeur k nous est donnée en entrée.

Donc, si l'entrée est quelque chose comme nombres = {2, 6, 4, 8}, k = 2, alors la sortie sera 2.

La différence entre les deux paires est -

(2, 6) = 4

(2, 4) = 2

(2, 8) = 6

(6, 4) = 2

(6 , 8) = 2

(4, 8) = 4

Si nous trions ces valeurs, cela devient 2, 2, 2, 4, 4, 6. La deuxième valeur minimale est 2. (indexé à partir de 0).

Pour résoudre ce problème, nous suivrons les étapes suivantes -

• Augmenter k de 1
• Trier l'entrée du tableau
• le := 0
• ri := Dernier élément d'entrée - Premier élément d'entrée
• while le
• mid := (le + ri) / 2
• tmp := 0
• lp := 0
• est utilisé pour initialiser i := 1, quand i
• while input[i] - input[lp] > mid, exécutez −
  • lp := lp + 1
• tmp := tmp + i - lp

if tmp >= k, alors -

• ri := mid

Sinon

• le := mid + 1

return le

Exemple

Regardons l'implémentation suivante pour mieux comprendre -

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

input

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

sortie

2

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!