※ 引述《JIWP (神楽めあ的钱包)》之铭言：
: 2134. Minimum Swaps to Group All 1's Together II
: nums矩阵由0、1组成，且nums为circular array
: 你可以任意将nums里面的两个元素互换位置
: 请问要将所有1元素集中在一起，最少需要交换几次
: 思路:
: 用sliding window
: 先计算1的数量，假设有n个
: 接着用大小为n的window去遍历nums
: 你要交换的次数就是n-window内1的数量
: 所以找出1最多的地方就好
: 然后因为nums是circular array所以要记得检查头尾连接的地方
: golang code :
: func minSwaps(nums []int) int {
: total, cnt, maxnum, n, idx := 0, 0, 0, len(nums), 0
: for _, val := range nums {
: total += val
: }
: for i := 0; i < total; i++ {
: cnt += nums[i]
: }
: maxnum = cnt
: for i := total; i < n; i++ {
: cnt += nums[i] - nums[idx]
: idx++
: maxnum = max(maxnum, cnt)
: }
: for i := 0; i < total-1; i++ {
: cnt += nums[i] - nums[idx]
: idx++
: maxnum = max(maxnum, cnt)
: }
: return total - maxnum
: }
思路:
sliding window 加加减减
先算one总数 之后算[0:one_sum]里面1的总数
之后窗户开滑 左边是1就减 右边是1就加
因为头尾相连所以做两次 大概这样
Python Code:
class Solution:
def minSwaps(self, nums: List[int]) -> int:
n = len(nums)
result = one_sum = sum(nums)
count = sum(nums[0:one_sum])
for i in range(one_sum,n*2):
count += (nums[i%n])
count -= (nums[(i-one_sum)%n])
result = min(result,one_sum-count)
return result