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_swaps

C语言：

#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)
}