배열의 모든 요소 쌍 사이에서 k번째로 작은 차이를 찾는 프로그램을 C++로 작성하세요.

여러 정수를 포함하는 목록이 있다고 가정해 보겠습니다. 배열에 있는 각 값 쌍의 차이를 찾고, 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 := 입력의 마지막 요소 - 입력의 첫 번째 항목
• while le
• mid := (le + ri) / 2
• tmp := 0
• lp := 0
• 은 i
• 입력[i] - 입력[lp] > mid, 실행 −
  • lp := lp + 1
• tmp := tmp + i - lp

if tmp >= k, then -

• ri := mid

그렇지 않으면

• le := mid + 1

return le

Example

더 잘 이해하기 위해 다음 구현을 살펴보겠습니다. -

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

출력

2

위 내용은 배열의 모든 요소 쌍 사이에서 k번째로 작은 차이를 찾는 프로그램을 C++로 작성하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!