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

逃离我推掉我的手 2023-09-24 13:39 39阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

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

### 题目来源 ###

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

### 题目描述 ###

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:68px;">输入</td> 
   <td style="width:430px;">[1,0,1,0,1]</td> 
  </tr> 
  <tr> 
   <td style="width:68px;">输出</td> 
   <td style="width:430px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:68px;">解释</td> 
   <td style="width:430px;"> <p>有三种可能的方法可以把所有的 1 组合在一起：</p> 
    <ul> 
     <li> <p>[1,1,1,0,0]，交换 1 次；</p> </li> 
     <li> <p>[0,1,1,1,0]，交换 2 次；</p> </li> 
     <li> <p>[0,0,1,1,1]，交换 1 次。</p> </li> 
    </ul><p>所以最少的交换次数为 1。</p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>输入</td> 
   <td>[0,0,0,1,0]</td> 
  </tr> 
  <tr> 
   <td>输出</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>解释</td> 
   <td>由于数组中只有一个 1，所以不需要交换。</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:69px;">输入</td> 
   <td style="width:429px;">[1,0,1,0,1,0,0,1,1,0,1]</td> 
  </tr> 
  <tr> 
   <td style="width:69px;">输出</td> 
   <td style="width:429px;">3</td> 
  </tr> 
  <tr> 
   <td style="width:69px;">解释</td> 
   <td style="width:429px;">交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

*  1 <= data.length <= 10^5
 *  0 <= data\[i\] <= 1

### 题目解析 ###

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

相同，解析请参考上面算法题。

注意本题输入数组的长度最长可以是10^5，因此算法时间复杂度不能是O(n^2)

### 算法源码 ###

[1151. _ 1 - _LeetCode]: https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together/
[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127418208?spm=1001.2014.3001.5501