2134. Minimum Swaps to Group All 1's Together II 使得所有1連在一起

 2134. Minimum Swaps to Group All 1's Together II  使得所有1連在一起

A swap is defined as taking two distinct positions in an array and swapping the values in them.

A circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all 1's present in the array together at any location.

 

Example 1:

Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Here are a few of the ways to group all the 1's together:
[0,0,1,1,1,0,0] using 1 swap.
[0,1,1,1,0,0,0] using 1 swap.
[1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array).
There is no way to group all 1's together with 0 swaps.
Thus, the minimum number of swaps required is 1.

Example 2:

Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Here are a few of the ways to group all the 1's together:
[1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array).
[1,1,1,1,1,0,0,0,0] using 2 swaps.
There is no way to group all 1's together with 0 or 1 swaps.
Thus, the minimum number of swaps required is 2.

Example 3:

Input: nums = [1,1,0,0,1]
Output: 0
Explanation: All the 1's are already grouped together due to the circular property of the array.
Thus, the minimum number of swaps required is 0.

 

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

考慮sliding window approach(window 大小就是 有多少個1) 考慮所有區間 count裡面有多少1 

之後 考慮所有的sliding window

複雜度O(n)

一加一減

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        
        num_1=sum(nums)
        
        res=num_1-sum(nums[:num_1])
        s=sum(nums[:num_1])
        for i in range(num_1,len(nums)):
            s+=nums[i]
            s-=nums[i-num_1]
            res=min(res,num_1-s)
        
        
        s=sum(nums[len(nums)-num_1+1:]+nums[:1])
        
        res=min(res,num_1-s)
        for i in range(1,num_1):
            s+=nums[i]
            s-=nums[len(nums)-num_1+i]
            res=min(res,num_1-s)
            
        return res