Yêu cầu hoán đổi tối thiểu để đưa tất cả các phần tử nhỏ hơn hoặc bằng k lại với nhau trong C ++

Tuyên bố vấn đề

Cho một mảng gồm n số nguyên dương và một số k. Tìm số lần hoán đổi tối thiểu cần thiết để đưa tất cả các số nhỏ hơn hoặc bằng k lại với nhau.

Ví dụ

Nếu mảng đầu vào là ={1, 5, 4, 7, 2, 10} và k =6 thì bắt buộc phải có 1 hoán đổi tức là hoán đổi phần tử 7 với 2.

Thuật toán

• Đếm tất cả các phần tử nhỏ hơn hoặc bằng ‘k’. Giả sử số lượng là "cnt"
• Sử dụng kỹ thuật hai con trỏ cho cửa sổ có độ dài ‘cnt’, mỗi lần theo dõi có bao nhiêu phần tử trong phạm vi này lớn hơn ‘k’. Giả sử tổng số là "outOfRange".
• Lặp lại bước 2, cho mọi cửa sổ có độ dài là ‘cnt’ và chiếm tối thiểu số lượng ‘outOfRange’ trong số đó. Đây sẽ là câu trả lời cuối cùng.

Ví dụ

#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 bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Đầu ra

Minimum swaps = 1