从Leetcode 每日一题练习继续讨论：
2134. 最少交换次数来组合所有的 1 II
2134. Minimum Swaps to Group All 1’s Together II
题解
本题中每个数组中1的数量是固定的, 我们先计数数组中1的个数后只要找到包含1数量最多的长度为数组全部1的数量的子数组, 则此子数组中0的个数即为最少的交换次数. 如何找到这样的子数组呢, 对于一个给定的数组, 因为1的数量固定, 则要找到满足条件的长度固定的子数组, 可以使用滑动窗口, 窗口长度设置为1的数量, 随着窗口滑动不断更新窗口中0的个数的最小值. 从数组开头开始滑动直到数组结尾. 最终得到的最小值即为最少交换次数.
代码
func minSwaps(nums []int) int {
countone := 0
for _,num := range nums{
if num == 1{
countone++
}
}
length := len(nums)
min0 := 0
current0 := 0
left := 0
right := countone-1
for _,num := range nums[0:countone]{
if num == 0{
min0++
}
}
current0 = min0
for left < length{
if nums[(right+1)%length] == 0{
current0++
}
if nums[left] == 0{
current0--
}
min0 = min(current0, min0)
left++
right++
}
return min0
}