在C ++中将所有小于或等于k的元素组合在一起所需的最小交换

问题陈述

给定一个n个正整数和一个数字k的数组。找到将所有小于或等于k的数字加在一起所需的最小交换数。

示例

如果输入数组= {1，5，4，7，2，10}且k = 6，则需要进行1次交换，即将元素7交换为2。

算法

• 计算所有小于或等于“ k”的元素。假设计数为“ cnt”

• 对长度为“ cnt”的窗口使用两个指针技术，每次跟踪该范围内有多少个元素大于“ k”。假设总数为“ outOfRange”。

• 对每个长度为“ cnt”的窗口重复步骤2，并在其中最小计数“ 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