leetcode在力扣 App 中打开
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
中等
相关标签
premium lock icon相关企业
提示

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

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

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

 

示例 1:

输入:nums = [0,1,0,1,1,0,0]
输出:1
解释:这里列出一些能够将所有 1 聚集在一起的方案:
[0,0,1,1,1,0,0] 交换 1 次。
[0,1,1,1,0,0,0] 交换 1 次。
[1,1,0,0,0,0,1] 交换 2 次(利用数组的环形特性)。
无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
因此,需要的最少交换次数为 1 。

示例 2:

输入:nums = [0,1,1,1,0,0,1,1,0]
输出:2
解释:这里列出一些能够将所有 1 聚集在一起的方案:
[1,1,1,0,0,0,0,1,1] 交换 2 次(利用数组的环形特性)。
[1,1,1,1,1,0,0,0,0] 交换 2 次。
无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
因此,需要的最少交换次数为 2 。

示例 3:

输入:nums = [1,1,0,0,1]
输出:0
解释:得益于数组的环形特性,所有的 1 已经聚集在一起。
因此,需要的最少交换次数为 0 。

 

提示:

  • 1 <= nums.length <= 105
  • nums[i]0 或者 1
通过次数
22,363/38.9K
通过率
57.5%

相关标签

icon
相关企业

提示 1
Notice that the number of 1’s to be grouped together is fixed. It is the number of 1's the whole array has.

提示 2
Call this number total. We should then check for every subarray of size total (possibly wrapped around), how many swaps are required to have the subarray be all 1’s.

提示 3
The number of swaps required is the number of 0’s in the subarray.

提示 4
To eliminate the circular property of the array, we can append the original array to itself. Then, we check each subarray of length total.

提示 5
How do we avoid recounting the number of 0’s in the subarray each time? The Sliding Window technique can help.


评论 (0)
💡 讨论区规则

1. 请不要在评论区发表题解!

2. 评论区可以发表关于对翻译的建议、对题目的疑问及其延伸讨论。

3. 如果你需要整理题解思路,获得反馈从而进阶提升,可以去题解区进行。

暂无评论

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
nums =
[0,1,0,1,1,0,0]
Source