最小交换以Python将所有1分组在一起
假设我们有一个二进制数组数据,我们必须找到将数组中所有1分组到一起的最小交换数。因此,如果数组像[1,0,1,0,1,0,0,1,1,0,1],则输出将为3,可能的解决方案是[0,0,0,0,0,1,1,1,1,1,1]
为了解决这个问题,我们将遵循以下步骤-
设置一个:=0,n:=数据数组的长度
生成大小为n的数组和,并用0填充,设置summ[0]:=data[0]
一:=一+数据[0]
当我在1到n–1的范围内时
summ[i]:=summ[i-1]+data[i]
一个:=一个+数据[i]
回答:=一个
左:=0,右:=1–1
而右<n
如果left为0,则temp:=summ[right],否则temp:=summ[right]–summ[left-1]
ans:=ans的最小值,一个–temp
左右增加1
返回ans
示例(Python)
让我们看下面的实现以更好地理解-
class Solution(object): def minSwaps(self, data): one = 0 n = len(data) summ=[0 for i in range(n)] summ[0] = data[0] one += data[0] for i in range(1,n): summ[i] += summ[i-1]+data[i] one += data[i] ans = one left = 0 right = one-1 while right <n: if left == 0: temp = summ[right] else: temp = summ[right] - summ[left-1] ans = min(ans,one-temp) right+=1 left+=1 return ans ob = Solution()print(ob.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))
输入值
[1,0,1,0,1,0,0,1,1,0,1]
输出结果
3