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입니다. (인덱스는 0부터 시작).

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

k를 1 증가
배열 입력 정렬
le :=0
ri :=입력의 마지막 요소 - 입력의 첫 번째 항목
le
중간 :=(le + ri) / 2
tmp :=0
lp :=0
초기화 i의 경우:=1, i <입력 크기일 때 업데이트(i 1만큼 증가), 수행 -
- 입력[i] 중 - 입력[lp]> mid, do -
  - lp :=lp + 1
- tmp :=tmp + i - lp
tmp> =k이면 -
- 리 :=중간
그렇지 않으면
- le :=중간 + 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;