P3257. 最少交换次数

解题思路

原数据的预处理

本题要求的是，将数组中所有小于 k 的元素都放在一起，放在一起后这些元素内部的顺序和大小其实无所谓。

因此，所有小于 k 的元素都可以归为一类，而大于等于 k 的元素可以归为另一类。 我们可以这样对原数组做预处理：将所有小于 k 的元素视为 0，将所有大于等于 k 的元素视为 1。

经过上述处理后，整个 nums 数组就只剩下 0 和 1 两种数字了。 譬如对于示例而言，nums 就会变为 nums = [0, 1, 0, 1, 0]。

其中 win_len 表示原数组中一共有多少个元素小于 k，或者说新数组中一共有多少个 0。 win_len 这个变量的作用，在后面会讲到。

问题就转变为：要将所有 0 移动到一起，最少需要进行几次交换。

将原问题转变为固定滑窗问题

题目中所谓的“交换”操作，是一个比较麻烦的过程。

对于一个只包含 0 和 1 的数组，如果我们想要将所有的 0 放到一起（一共 win_len 个 0），这些 0 最终的分布的状态只可能是一个原数组中一个长度为 win_len 的连续子数组。

譬如对于 nums = [0, 1, 0, 1, 0]，其交换后最终状态只可能是

或

或

中的一种。

那么，在这些连续子数组中，我们会选择哪一个作为最终状态呢？ 这取决于这个连续子数组原来包含了多少 0，换言之有多少 1 的空位是需要从数组外的 0 交换过来的。

如果想要得到结果 nums = [0, 0, 0, 1, 1]，我们会将 nums = [0, 1, 0, 1, 0] 中索引为 1 的 1 和索引为 4 的 0 进行交换。这样只需要交换 1 次。

譬如，如果想要得到结果 nums = [1, 0, 0, 0, 1]，我们会将 nums = [0, 1, 0, 1, 0] 中索引为 1 和 3 的两个 1 和索引为 0 和 4 的两个 0 进行交换。这样需要交换 2 次。

显然，当原连续子数组包含的 0 越多，需要交换的次数越少。 换言之，包含的 1 越少，需要交换的次数越少。因为这些 1 最终都会通过交换而被数组外的 0 代替。

对于长度为 win_len 的子数组，当其初始状态包含 win_1 个 1 的时候，以这个连续子数组作为最终连续 0 的排布所需要的交换次数为 win_1。

因此，这个问题就转变为了一个固定滑窗问题。 我们需要找到一个长度为 win_len 的固定滑窗，其包含的 1 的个数尽可能少，最小的个数记为答案。

剩下的内容就是使用滑窗三问三答秒杀了。

如果没想到能转化为固定滑窗算法，也可以尝试使用蒙特卡洛模拟的方法来进行。感兴趣的同学可以自行尝试。

复杂度分析 设 n 为数组 nums 的长度，win_len 为数组中小于 K 的元素个数（也就是固定窗口的长度）。

• 时间复杂度：O(n)。整个算法是三段线性工作：第一趟遍历把每个元素就地改写成 0（小于 K）或 1（大于等于 K），同时统计出 win_len，O(n)；初始化第一个窗口、统计前 win_len 个元素里 1 的个数 win_1，O(win_len)；固定滑窗从下标 win_len 推进到数组末尾，每一步只做「新进元素是 1 则 win_1 加一、滑出元素是 1 则 win_1 减一、用 win_1 更新最小值 ans」三个 O(1) 操作，合计 O(n)。三段相加仍是线性，瓶颈是对数组的两趟扫描。
• 空间复杂度：O(1)（不计输入数组）。预处理直接在原数组上就地改写为 0/1，没有开辟新数组；其余只有 win_1、ans、left 等常数个变量。

这也印证了转化的价值：把「最少交换次数」翻译成「长度为 win_len 的窗口里 1 的个数的最小值」之后，问题只需线性时间就能解决。