คำชี้แจงปัญหา
กำหนดอาร์เรย์ของจำนวนเต็มบวก n และจำนวน k หาจำนวนสวอปขั้นต่ำที่จำเป็นในการนำตัวเลขทั้งหมดที่น้อยกว่าหรือเท่ากับ k มารวมกัน
ตัวอย่าง
หากอาร์เรย์อินพุตคือ ={1, 5, 4, 7, 2, 10} และ k =6 จำเป็นต้องมีการสลับ 1 ครั้ง เช่น สลับองค์ประกอบ 7 กับ 2
อัลกอริทึม
- นับองค์ประกอบทั้งหมดที่น้อยกว่าหรือเท่ากับ 'k' สมมติว่าการนับคือ 'cnt'
- ใช้เทคนิคตัวชี้สองตัวสำหรับหน้าต่างที่มีความยาว 'cnt' แต่ละครั้งจะติดตามว่ามีองค์ประกอบกี่องค์ประกอบในช่วงนี้ที่มากกว่า 'k' สมมติว่าจำนวนทั้งหมดเป็น "outOfRange"
- ทำซ้ำขั้นตอนที่ 2 สำหรับทุกหน้าต่างที่มีความยาว 'cnt' และนับ 'outOfRange' ให้น้อยที่สุด นี่จะเป็นคำตอบสุดท้าย
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n, int k) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] <= k) {
++cnt;
}
}
int outOfRange = 0;
for (int i = 0; i < cnt; ++i) {
if (arr[i] > k) {
++outOfRange;
}
}
int result = outOfRange;
for (int i = 0, j = cnt; j < n; ++i, ++j) {
if (arr[i] > k) {
--outOfRange;
}
if (arr[j] > k) {
++outOfRange;
}
result = min(result, outOfRange);
}
return result;
}
int main() {
int arr[] = {1, 5, 4, 7, 2, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 6;
cout << "Minimum swaps = " << getMinSwaps(arr, n, k) <<
endl;
return 0;
} เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Minimum swaps = 1
