Đề bài
Cho mảng n số nguyên dương và số k. Tìm số lần hoán vị tối thiểu để gom tất cả số nhỏ hơn hoặc bằng k lại với nhau.
Ví dụ
Nếu mảng đầu vào = {1, 5, 4, 7, 2, 10} và k = 6 thì cần 1 lần hoán vị, tức hoán vị phần tử 7 với 2.
Thuật toán
- Đếm tất cả phần tử nhỏ hơn hoặc bằng 'k'. Giả sử đếm được 'cnt'
- Dùng kỹ thuật hai con trỏ cho cửa sổ độ dài 'cnt', mỗi lần theo dõi bao nhiêu phần tử trong khoảng lớn hơn 'k'. Giả sử tổng đếm là 'outOfRange'.
- Lặp lại bước 2 cho mọi cửa sổ độ dài 'cnt' và lấy min của 'outOfRange'. Đó là đáp án cuối cùng.
Ví dụ mã nguồn
#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; } Khi biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
Minimum swaps = 1