C++の配列内のすべての要素ペア間のk番目に小さい差を見つけるプログラム

いくつかの整数を含むリストが与えられたとしましょう。配列内の値の各ペア間の差を見つけ、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番目に小さい値は2です（インデックスは0から始まります）。

これを解決するには、次の手順に従います-

• kを1増やします
• 配列入力を並べ替える
• le：=0
• ri：=入力の最後の要素-入力の最初の項目
• le を実行します
• 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

例

理解を深めるために、次の実装を見てみましょう-

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

出力

2