本文主要是介绍leetcode 2134.最少交换次数来组合所有的1 Ⅱ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
题目描述
示例1：
示例2：
示例3：
提示：
解题思路
滑动窗口法
概念
应用场景及特点：
思路
代码
复杂度分析
优化解法
代码实现
Python语言：
C语言：
Go语言：
优化后的代码解释
优化后的复杂度分析
题目描述
交换定义为选中一个数组中的两个互不相同的位置并交换二者的值。
环形数组是一个数组，可以认为第一个元素和最后一个元素相邻 。
给你一个二进制环形数组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
解题思路
滑动窗口法
概念
滑动窗口是一个在序列上移动的区间，通常由左右两个指针来界定这个区间的范围。通过移动指针来改变窗口的大小和位置，在窗口移动的过程中，根据问题的需求进行特定的计算和处理。
应用场景及特点：
- 子数组 / 子串问题：
- 当需要在一个序列中找到满足特定条件的连续子数组或子串时，滑动窗口非常适用。例如，寻找和为特定值的连续子数组、含有特定字符的最长子串等。
- 窗口的大小通常是动态变化的，根据问题的条件进行调整。
- 高效性：
- 相比于暴力枚举所有可能的子数组 / 子串，滑动窗口法通常能够在更短的时间内找到解。因为它利用了子数组 / 子串的连续性和窗口的滑动特性，避免了重复计算。
- 指针移动规则：
- 通常有两个指针，一个指向窗口的左端，一个指向窗口的右端。根据问题的具体要求，以特定的方式移动指针。
- 例如，在寻找满足特定条件的最小子数组时，可能会先扩大窗口直到满足条件，然后再缩小窗口以找到最小的满足条件的窗口。
思路
- 统计 1 的总数：
- 首先计算数组
nums中的 1 的总数，记为k。因为我们需要把这些 1 聚集在一起，所以我们需要在数组中找到包含k个元素的连续子数组，使得该子数组中的 0 的数量最少。
- 扩展环形数组：
- 由于数组是环形的，我们可以将数组扩展一倍，即将数组
nums复制一遍并连接到原数组后面，得到新的数组nums_ext。这使得我们可以在新的数组中处理环形问题就像处理线性问题一样。
- 滑动窗口：
- 使用一个长度为
k的滑动窗口，在nums_ext上滑动，统计每个窗口内的 0 的数量。 - 记录所有窗口中 0 的最小数量，即为将 1 聚集在一起所需的最少交换次数。
- 输出结果：
- 计算结果为 0 的最小值，即为我们需要的最少交换次数。
代码
class Solution:def minSwaps(self, nums: List[int]) -> int:# 步骤1：统计1的总数k = sum(nums)n = len(nums)if k == 0 or k == n:return 0# 步骤2：扩展环形数组nums_ext = nums + nums# 步骤3：滑动窗口min_swaps = float('inf')current_zeros = 0# 初始化第一个窗口for i in range(k):if nums_ext[i] == 0:current_zeros += 1min_swaps = current_zeros# 滑动窗口遍历剩余部分for i in range(1, n):if nums_ext[i-1] == 0:current_zeros -= 1if nums_ext[i+k-1] == 0:current_zeros += 1min_swaps = min(min_swaps, current_zeros)return min_swaps复杂度分析
- 时间复杂度：O(n)，因为我们需要遍历数组
nums_ext。 - 空间复杂度：O(n)，因为我们构建了一个双倍长度的数组
nums_ext。
优化解法
- 计算 1 的总数：首先统计数组中 1 的数量
k，我们仍然需要这个值来确定滑动窗口的大小。 - 滑动窗口：直接在原数组
nums上进行滑动窗口操作。由于数组是环形的，当滑动窗口超出数组长度时，可以使用取模操作来访问数组中的元素。 - 跟踪最小的 0 的数量：跟踪窗口中 0 的最小数量，这将对应最少的交换次数。
代码实现
Python语言：
class Solution:def minSwaps(self, nums: List[int]) -> int:k = sum(nums) # 计算1的总数n = len(nums)if k == 0 or k == n:return 0# 初始窗口内的0的数量current_zeros = sum(1 for i in range(k) if nums[i] == 0)min_swaps = current_zeros# 滑动窗口遍历数组，利用环形特性for i in range(1, n):# 移出窗口的元素if nums[i - 1] == 0:current_zeros -= 1# 加入窗口的元素if nums[(i + k - 1) % n] == 0:current_zeros += 1# 更新最小交换次数min_swaps = min(min_swaps, current_zeros)return min_swapsC语言：
#include <stdio.h>int minSwaps(int nums[], int n) {int k = 0;for (int i = 0; i < n; i++) {k += nums[i];}if (k == 0 || k == n) {return 0;}int current_zeros = 0;for (int i = 0; i < k; i++) {if (nums[i] == 0) {current_zeros++;}}int min_swaps = current_zeros;for (int i = 1; i < n; i++) {if (nums[i - 1] == 0) {current_zeros--;}if (nums[(i + k - 1) % n] == 0) {current_zeros++;}if (current_zeros < min_swaps) {min_swaps = current_zeros;}}return min_swaps;
}int main() {int nums[] = {1, 0, 1, 0, 1, 0, 0, 1};int n = sizeof(nums) / sizeof(nums[0]);int result = minSwaps(nums, n);printf("Minimum swaps required: %d\n", result);return 0;
}Go语言：
package mainimport ("fmt"
)func minSwaps(nums []int) int {k := 0n := len(nums)for _, num := range nums {k += num}if k == 0 || k == n {return 0}currentZeros := 0for i := 0; i < k; i++ {if nums[i] == 0 {currentZeros++}}minSwaps := currentZerosfor i := 1; i < n; i++ {if nums[i-1] == 0 {currentZeros--}if nums[(i+k-1)%n] == 0 {currentZeros++}if currentZeros < minSwaps {minSwaps = currentZeros}}return minSwaps
}func main() {nums := []int{1, 0, 1, 0, 1, 0, 0, 1}result := minSwaps(nums)fmt.Println("Minimum swaps required:", result)
}优化后的代码解释
- 滑动窗口：在原数组上直接滑动窗口，而不需要构造扩展数组。
- 环形数组的处理：使用
(i + k - 1) % n的取模运算来访问数组的后续元素，这样可以有效处理数组的环形特性。
优化后的复杂度分析
- 时间复杂度：O(n)，我们只需遍历数组一次。
- 空间复杂度：O(1)，因为没有使用额外的空间。
这篇关于leetcode 2134.最少交换次数来组合所有的1 Ⅱ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
