整数数组nums,整数k。输出将数组A中小于k的整数组合到一起的最小交换次数。组合在一起是指满足条件的数字相邻,不要求相邻后在数组中的位置。
样例1:
nums=[1,3,1,4,0], k=2
输出:1 ,解析:交换第一个1和4
样例2:
nums=[0,0,0,1,0], k=2
输出:0,解析:已经满足条件
样例3:
nums=[2,3,2], k=1
输出:0,解析:不存在小于k的数,无需交换
public static void main(String[] args) {
int target = 2;
//int[] arr = {0, 0, 0, 1, 0};
int[] arr = {1, 3, 1, 4, 0};
//int[] arr = {2, 3, 2};
int totalLess = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < target) {
totalLess++;
}
}
//有一个滑动窗口,窗口大小固定为小于target的数,然后但凡在窗口内不小于的,就是需要交换的
int res = Integer.MAX_VALUE;
for (int i = 0; i < arr.length + 1 - totalLess; i++) {
int count = 0;
for (int j = 0; j < totalLess; j++) {
if (arr[i + j] > target) {
count++;
}
}
res = Math.min(res, count);
}
System.out.println(res);
}