数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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
更新于：2019年12月20日
393 次浏览
广告