LeetCode - 1703 得到连续 K 个 1 的最少相邻交换次数

r囧r小猫 2023-09-24 13:40 16阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[1703. 得到连续 K 个 1 的最少相邻交换次数 - 力扣（LeetCode）][1703. _ K _ 1 _ - _LeetCode]

### 题目描述 ###

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择 相邻 两个数字并将它们交换。

请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:67px;">输入</td> 
   <td style="width:431px;">nums = [1,0,0,1,0,1], k = 2</td> 
  </tr> 
  <tr> 
   <td style="width:67px;">输出</td> 
   <td style="width:431px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:67px;">解释</td> 
   <td style="width:431px;">在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:67px;">输入</td> 
   <td style="width:431px;">nums = [1,0,0,0,0,0,1,1], k = 3</td> 
  </tr> 
  <tr> 
   <td style="width:67px;">输出</td> 
   <td style="width:431px;">5</td> 
  </tr> 
  <tr> 
   <td style="width:67px;">解释</td> 
   <td style="width:431px;">通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:68px;">输入</td> 
   <td style="width:430px;">nums = [1,1,0,1], k = 2</td> 
  </tr> 
  <tr> 
   <td style="width:68px;">输出</td> 
   <td style="width:430px;">0</td> 
  </tr> 
  <tr> 
   <td style="width:68px;">解释</td> 
   <td style="width:430px;">nums 已经有连续 2 个 1 了。</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

*  `1 <= nums.length <= 105`
 *  `nums[i]` 要么是 `0` ，要么是 `1` 。
 *  `1 <= k <= sum(nums)`

### 题目解析 ###

本题和前面的

[算法 - 最少交换次数来组合所有的1\_伏城之外的博客-CSDN博客][- _1_-CSDN]

[算法 - 最少交换次数\_伏城之外的博客-CSDN博客][- _-CSDN]

题目类似，区别在于本题：“每一次移动，你可以选择 相邻 两个数字并将它们交换。”

而前面两题的交换是任意两个位置的数字可以直接交换。

因此本题的滑窗设计和前面略有不同。

比如

nums = \[1,0,0,1,0,1\], k = 2

如果才有下面这种滑窗设计，则是非常低效，不仅滑窗移动次数多，并且需要判断滑窗外部的1来到滑窗内部的最近距离

![aa425ebc66654f52a1c3a57bc643cc1c.png][]

因此，我们不能采用上面滑窗设计。

题目要求，我们要让K个1组合到一起，我们可以直接让滑窗内含有K个1即可，如下

![af33420441a94e4ebca0c5ab2b073806.png][]

可以发现，此时滑窗情况大大减少，并且我们只需要关注滑窗内部K个1的移动即可，不需要关注滑窗外部的1。

但是此时滑窗的移动是非连续的，如上图，第一个滑窗起始位置是0，第二个滑窗起始位置直接跳到了3，但是我们可以换个角度看问题，第一个滑窗的起始位置是第一个1，第二个滑窗位置起始位置是第二个1，这样看的话，滑窗的移动就是连续的了。

因此我们需要统计输入数列中1的位置，将输入数列转为1位置数列，如下图所示

![cb03e4db52454216aca71c474a56b61f.png][]

此时滑窗移动就可以转为下面连续情况

![761e51bb241542348253ab525cc8c801.png][]

滑窗的移动问题解决后，我们就可以着手解决滑窗内部K个1组合到一起的问题，比如下面情况，

![0ff168b4a06b46e49f472215f85969e1.png][]

我们需要将索引0的一和索引3的一组合到一起，则可以让有两种方式：

1.  将索引0的一交换到索引2的位置，即2-0，需要交换2次
2.  将索引3的一交换到索引1的位置，即3-1，需要交换2次

上面两种方式是等价的。

我们将nums中1元素的索引选取出来定义为数组ones，

![31b4bd4639654704914d522e6dba3cdb.png][]

则当K=2时，每种滑窗情况需要交换：

*  ones\[1\] - ones\[0\] 次
 *  ones\[2\] - ones\[1\] 次
 *  ....
 *  ones\[ones.length - 1\] - ones\[ones.length - 2\] 次

我们比较上面每种滑窗的交换次数，取最小值。

上面是K=2时的情况，算是特殊情况，下面我们看下K>2的情况，比如

输入数组nums = \[0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0\]，K=7

则滑窗情况如下

![3118200d570c4de0ba4a7f59b72a06b0.png][]

此时，我们会发现想要将7个1组合到一起，则情况非常多，比如第一种滑窗情况，我们可以选取一个1的位置，然后让剩余的1都往选取1的位置靠拢，那么就会有K种移动策略，我们要选取其中移动次数最少的那种策略。那么选取哪个位置的1的移动次数最少呢？

答案是中间位置的1。

> 我们通过下面例子来理解
> 
> ![4f3608b8532949b9a98e931d05a51599.png][]
> 
> 可以发现，向中间位置的1靠拢所花费的交换次数是最少的。

因此我们需要求解出滑窗内，中间位置的1的索引，求解方程如下

i + Math.floor(k/2)，

i 是滑窗中第一个1的索引位置（注意 i 取自ones数组，而不是nums数组），k就是滑窗内1的个数

公式最终结果也是ones数组的索引位置

![b7c06b4c6ad74d1791ed06a6a81911ad.png][]

比如上面图示中，第一个滑窗情况中间位置的1的所有是：0 + Math.floor(7/2) = 3，即ones\[3\]就是滑窗内中间位置1的索引。

求得中间位置1后，我们就可以让两边的1往中间位置1靠拢，比如上面第一个滑窗情况，中间位置1的索引是7，而中间位置左边有3个1，右边有3个1，因此

我们需要预留索引4,5,6给左边的1，预留8,9,10索引给右边的1。

即如下图中，橙色部分就是预留位置

![cd97a7158496473f8858bc9b1d32dcf3.png][]

此时我们发现预留位置上已经有1了，因此我们判断如果预留位置有1的话，则跳过，但是这种方式会增加判断逻辑，让本就复杂的算法更加复杂。

实际上，我们有两种移动策略，让左边的1到预留位置

![ca3a7f5193e74f51a46e292aa36bb27a.png][]

第一种，如上图，需要交换5次

![40833584472647e3911ffc53786627e7.png][]

第二种，如上图，需要交换5次

因此上面两种方式其实是等价的。但是第二种方式用代码实现起来更简单。

同理我们可以让中间位置1的右边1移动到预留位置

![aa29fe94e220472a96469f2a324e20c8.png][]

上面是基于nums的角度看的，我们再换一个视角用ones来看，红色数字就是预留位置

![3ece4d35a75f4dc7aedfad007250d478.png][]

即让 左边的 索引5交换到6，4交换到5，1交换到4，交换次数一共是 (6-5) + (5-4) + (4-1) = 5

让 右边的 索引9交换到8，10交换到9，11交换到10 ，交换次数一共是 (9-8) + (10-9) + (11-10) = 3

因此，每一种滑窗都需花费O(K)的时间复杂度来计算最少交换次数。

![b7c06b4c6ad74d1791ed06a6a81911ad.png][]

而滑窗的情况有O(ones.length - K + 1)，差不多是O(n)复杂度，因此计算所有滑窗情况种的最少交换次数需要O(n^2)复杂度，并不符合题目要求。

因此我们需要优化。

下面是起始位置在第1个一的滑窗和 起始位置在第2个一的滑窗，它们存在交集区域，如下红框

![ff023feb3a7a4861a59a42128ef77cc7.png][]

这两个交集区域是有关系的，它们其中元素相同，而中心位置不同，但是中心位置是相邻的

![1e94f4c253f3474aae0a28a96627921d.png][]

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:91px;"></td> 
   <td style="width:184px;">第一个滑窗</td> 
   <td style="width:224px;">第二个滑窗</td> 
  </tr> 
  <tr> 
   <td style="width:91px;">4</td> 
   <td style="width:184px;">→ 5&nbsp; &nbsp; &nbsp; &nbsp;交换次数+1</td> 
   <td style="width:224px;">→ 6&nbsp; &nbsp;&nbsp;交换次数+2</td> 
  </tr> 
  <tr> 
   <td style="width:91px;">5</td> 
   <td style="width:184px;">→ 6&nbsp; &nbsp; &nbsp; &nbsp;交换次数+1</td> 
   <td style="width:224px;">→ 7&nbsp; &nbsp;交换次数+2</td> 
  </tr> 
  <tr> 
   <td style="width:91px;">7</td> 
   <td style="width:184px;">中心位置，两边向我靠拢</td> 
   <td style="width:224px;">→ 8&nbsp; &nbsp;交换次数+1</td> 
  </tr> 
  <tr> 
   <td style="width:91px;">9</td> 
   <td style="width:184px;">→ 8&nbsp; &nbsp; &nbsp;&nbsp;交换次数+1</td> 
   <td style="width:224px;">中心位置，两边向我靠拢</td> 
  </tr> 
  <tr> 
   <td style="width:91px;">10</td> 
   <td style="width:184px;">→ 9&nbsp; &nbsp; &nbsp;&nbsp;交换次数+1</td> 
   <td style="width:224px;">→ 10&nbsp;&nbsp;交换次数+0</td> 
  </tr> 
  <tr> 
   <td style="width:91px;">11</td> 
   <td style="width:184px;">→ 10&nbsp; &nbsp;&nbsp;交换次数+1</td> 
   <td style="width:224px;">→ 11&nbsp;&nbsp;交换次数+0</td> 
  </tr> 
 </tbody> 
</table>

我们可以发现，中心位置从7变为9后，左边元素4,5的交换次数在原有基础上多加了一次，而这多出来的一次，其实就是上一次中心位置7 交换到 本次中心位置9 左边的8后，多出来的一次。

而右边元素10,11在原有基础上少了一次，二者少的一次，也是上一次中心位置7 交换到 本次中心位置9 左边的8后的影响导致的。

而无论是9到中心位置7的右边8，还是7到中心位置9的左边8的交换次数都是相同的。因此上面两个滑窗交集区域的交换次数差别，取决于7左边（不包含7）元素新增的交换次数，和9右边（不包含9）元素减少的交换次数 的 总和。

上面情况滑窗中元素个数刚好是奇数个，因此两个滑窗交集区域的7左边元素和9右边元素的个数是相同的，因此两个交集区域的交换次数是相等的。

如果滑窗中元素个数是偶数个，则此时导致两个滑窗的交集区域的交换次数不一致，如下例所示

![832610afe38c4079a9159ce7d6566983.png][]

上面图示中，第二个滑窗的交集区域要比第一个滑窗的交集区域的交换次数 多1次 。

当我们知道了两次滑窗交集区域的交换次数 关系后，我们就可以避免重新计算每一个元素到中心位置的交换次数了，直接基于推导的关系计算出来即可。

而滑窗在向右移动一次后，就会失去一个元素，比如上图失去了ones\[0\]，新增了ones\[26\]

因此，我们只需要在上一个滑窗的交换次数基础上，减去ones\[0\]到上一次的中心位置one\[13\]的交换次数，加上ones\[26\]到本次的中心位置ones\[14\]的交换次数，再加上两次滑窗交叉区域的差异交换次数，就是最终的题解。

### 算法源码 ###

![11b8d504fd9045a5a8159060616e437a.png][]

[1703. _ K _ 1 _ - _LeetCode]: https://leetcode.cn/problems/minimum-adjacent-swaps-for-k-consecutive-ones/
[- _1_-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127507253?spm=1001.2014.3001.5501
[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127418208?spm=1001.2014.3001.5501
[aa425ebc66654f52a1c3a57bc643cc1c.png]: https://img-blog.csdnimg.cn/aa425ebc66654f52a1c3a57bc643cc1c.png
[af33420441a94e4ebca0c5ab2b073806.png]: https://img-blog.csdnimg.cn/af33420441a94e4ebca0c5ab2b073806.png
[cb03e4db52454216aca71c474a56b61f.png]: https://img-blog.csdnimg.cn/cb03e4db52454216aca71c474a56b61f.png
[761e51bb241542348253ab525cc8c801.png]: https://img-blog.csdnimg.cn/761e51bb241542348253ab525cc8c801.png
[0ff168b4a06b46e49f472215f85969e1.png]: https://img-blog.csdnimg.cn/0ff168b4a06b46e49f472215f85969e1.png
[31b4bd4639654704914d522e6dba3cdb.png]: https://img-blog.csdnimg.cn/31b4bd4639654704914d522e6dba3cdb.png
[3118200d570c4de0ba4a7f59b72a06b0.png]: https://img-blog.csdnimg.cn/3118200d570c4de0ba4a7f59b72a06b0.png
[4f3608b8532949b9a98e931d05a51599.png]: https://img-blog.csdnimg.cn/4f3608b8532949b9a98e931d05a51599.png
[b7c06b4c6ad74d1791ed06a6a81911ad.png]: https://img-blog.csdnimg.cn/b7c06b4c6ad74d1791ed06a6a81911ad.png
[cd97a7158496473f8858bc9b1d32dcf3.png]: https://img-blog.csdnimg.cn/cd97a7158496473f8858bc9b1d32dcf3.png
[ca3a7f5193e74f51a46e292aa36bb27a.png]: https://img-blog.csdnimg.cn/ca3a7f5193e74f51a46e292aa36bb27a.png
[40833584472647e3911ffc53786627e7.png]: https://img-blog.csdnimg.cn/40833584472647e3911ffc53786627e7.png
[aa29fe94e220472a96469f2a324e20c8.png]: https://img-blog.csdnimg.cn/aa29fe94e220472a96469f2a324e20c8.png
[3ece4d35a75f4dc7aedfad007250d478.png]: https://img-blog.csdnimg.cn/3ece4d35a75f4dc7aedfad007250d478.png
[ff023feb3a7a4861a59a42128ef77cc7.png]: https://img-blog.csdnimg.cn/ff023feb3a7a4861a59a42128ef77cc7.png
[1e94f4c253f3474aae0a28a96627921d.png]: https://img-blog.csdnimg.cn/1e94f4c253f3474aae0a28a96627921d.png
[832610afe38c4079a9159ce7d6566983.png]: https://img-blog.csdnimg.cn/832610afe38c4079a9159ce7d6566983.png
[11b8d504fd9045a5a8159060616e437a.png]: https://img-blog.csdnimg.cn/11b8d504fd9045a5a8159060616e437a.png