在 Python 中将所有 1 组合在一起的最小交换次数
pythonserver side programmingprogramming
假设我们有一个二进制数组数据，我们必须找到将数组中存储的所有 1 组合在数组中任意位置所需的最小交换次数。因此，如果数组类似于 [1,0,1,0,1,0,0,1,1,0,1]，则输出将为 3，因为可能的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]
要解决这个问题，我们将遵循以下步骤 −
- 设置 one := 0，n:= 数据数组的长度
- 创建一个大小为 n 的数组 summ，并用 0 填充，设置 summ[0] := data[0]
- one := one + data[0]
- 对于 i 在 1 到 n 的范围内 – 1
- summ[i] := summ[i - 1] + data[i]
- one := one + data[i]
- ans := one
- left := 0, right := one – 1
- while right < n
- 如果 left 为 0，则 temp := summ[right]，否则 temp := summ[right] – summ[left - 1]
- ans := ans 的最小值，one – temp
- 将 right 和 left 增加 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
