LeetCode - 2134 最少交换次数来组合所有的 1 II

谁借莪１个温暖的怀抱￠ 2023-09-24 13:39 78阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

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

### 题目来源 ###

[2134. 最少交换次数来组合所有的 1 II - 力扣（LeetCode）][2134. _ 1 II - _LeetCode]

### 题目描述 ###

交换定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。

环形数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。

给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:54px;">输入</td> 
   <td style="width:444px;">nums = [0,1,0,1,1,0,0]</td> 
  </tr> 
  <tr> 
   <td style="width:54px;">输出</td> 
   <td style="width:444px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:54px;">解释</td> 
   <td style="width:444px;">这里列出一些能够将所有 1 聚集在一起的方案： 
    <ul> 
     <li>[0,0,1,1,1,0,0] 交换 1 次。</li> 
     <li>[0,1,1,1,0,0,0] 交换 1 次。</li> 
     <li>[1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。</li> 
    </ul> 无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。<br> 因此，需要的最少交换次数为 1 。</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:54px;">输入</td> 
   <td style="width:444px;">nums = [0,1,1,1,0,0,1,1,0]</td> 
  </tr> 
  <tr> 
   <td style="width:54px;">输出</td> 
   <td style="width:444px;">2</td> 
  </tr> 
  <tr> 
   <td style="width:54px;">解释</td> 
   <td style="width:444px;">这里列出一些能够将所有 1 聚集在一起的方案： 
    <ul> 
     <li>[1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。</li> 
     <li>[1,1,1,1,1,0,0,0,0] 交换 2 次。</li> 
    </ul> 无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。<br> 因此，需要的最少交换次数为 2 。</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>输入</td> 
   <td>nums = [1,1,0,0,1]</td> 
  </tr> 
  <tr> 
   <td>输出</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>解释</td> 
   <td>得益于数组的环形特性，所有的 1 已经聚集在一起。<br> 因此，需要的最少交换次数为 0 。</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

*  `1 <= nums.length <= 105`
 *  `nums[i]` 为 `0` 或者 `1`

### 题目解析 ###

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

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

题目的区别，在于本题是环形数组，上面两个题目的数组不是环形的。

但是环形数组并不意味着难度更大，只是单纯地扩展了组合的情况而已，如下图所示

![8c559fed4c764dd0b12d7c47f5dc35de.png][]

因此，只要在前面算法题的解题思路上，扩展一些情况即可

### 算法源码 ###

![a9b7a82399474b2dbb51ed4756c8b3be.png][]

[2134. _ 1 II - _LeetCode]: https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/
[- _1_-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127507253
[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127418208
[8c559fed4c764dd0b12d7c47f5dc35de.png]: https://img-blog.csdnimg.cn/8c559fed4c764dd0b12d7c47f5dc35de.png
[a9b7a82399474b2dbb51ed4756c8b3be.png]: https://img-blog.csdnimg.cn/a9b7a82399474b2dbb51ed4756c8b3be.png