Chương trình tìm ra sự khác biệt nhỏ nhất thứ k giữa tất cả các cặp phần tử trong một mảng trong C ++

Giả sử chúng ta được cung cấp một danh sách chứa một số số nguyên. Chúng ta phải tìm ra sự khác biệt giữa từng cặp giá trị trong mảng và tìm ra số chênh lệch nhỏ nhất thứ k. Chỉ mục bắt đầu từ 0 và giá trị k được cung cấp cho chúng tôi làm đầu vào.

Vì vậy, nếu đầu vào là số ={2, 6, 4, 8}, k =2, thì đầu ra sẽ là 2.

Sự khác biệt giữa các cặp là -

(2, 6) =4

(2, 4) =2

(2, 8) =6

(6, 4) =2

(6, 8) =2

(4, 8) =4

Nếu chúng ta sắp xếp các giá trị, nó sẽ trở thành 2, 2, 2, 4, 4, 6. Giá trị nhỏ nhất thứ 2 là 2. (Chỉ mục bắt đầu từ 0).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tăng k thêm 1
• sắp xếp đầu vào mảng
• le:=0
• ri:=phần tử cuối cùng của đầu vào - mục đầu tiên của đầu vào
• while le
• giữa:=(le + ri) / 2
• tmp:=0
• lp:=0
• để khởi tạo i:=1, khi i
• while input [i] - input [lp]> mid, do -
  • lp:=lp + 1
• tmp:=tmp + i - lp

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

2