สมมติว่าเราได้รับรายการที่มีตัวเลขจำนวนเต็มหลายจำนวน เราต้องหาความแตกต่างระหว่างค่าแต่ละคู่ในอาร์เรย์และหาค่าความแตกต่างน้อยที่สุดที่ 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
- จัดเรียงอินพุตอาร์เรย์
- เล :=0
- ri:=องค์ประกอบสุดท้ายของอินพุต - รายการแรกของอินพุต
- ในขณะที่ le
- กลาง :=(le + ri) / 2
- tmp :=0
- lp :=0
- สำหรับการเริ่มต้น i :=1 เมื่อฉัน <ขนาดของอินพุต อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
- ในขณะที่อินพุต[i] - อินพุต[lp]> กลาง ทำ −
- lp :=lp + 1
- tmp :=tmp + i - lp
- ถ้า tmp> =k แล้ว −
- ริ :=กลาง
- มิฉะนั้น
- 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
