※ 引述《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