algorithm - 分隔 0 和 1 列表所需的最少相邻交换数是多少？

Question

我正在尝试解决一个数据结构和算法问题，该问题指出给定一组 1 和 0，将数字分组，使所有 0 和所有 1 都在一起。如果只能交换两个相邻元素，完成此操作所需的最少交换次数是多少？哪个组在哪一端并不重要。

例如:

[0,1,0,1] = [0,0,1,1] 1 次交换

[1,1,1,1,0,1,0] = [1,1,1,1,1,0,0] 1 次交换

[1, 0, 1, 0, 0, 0, 0, 1] = = [1,1,1,0,0,0,0,0] 6 次交换

请注意，这与此处提出的问题不同:

Find the minimum number of swaps required such that all the 0s and all the 1s are together

我不是在对数组进行排序，我只是想将所有 0 和所有 1 组合在一起，哪个在哪​​一端并不重要。

我真的不知道从哪里开始。有人可以帮助我吗？

Answer 1

让我们关注零。每次互换都会将单个零移动一个位置，使其更接近最终订单。然后我们可以通过找到置换零的数量和置换的严重程度来找到交换的数量。

让我们首先假设零在数组的开头结束。我们将跟踪两件事:count_of_ones 和位移，都初始化为零。每次找到 1 时，我们都会增加 count_of_ones。每次找到 0 时，我们都会将位移增加 count_of_ones。

然后我们从另一个方向来做。两种方式都是线性的，所以这是线性的。

例如1010001

1: count_of_ones: 0 -> 1
0: displacement: 0 -> 1
1: count_of_ones: 1 -> 2
0: displacement: 1 -> 3
0: displacement: 3 -> 5
0: displacement: 5 -> 7
1: count_of_ones: 2 -> 3

这个方向的答案是最终位移，即 7。反过来我们得到 5。最终答案是 5。

事实上，最终位移的总和(开始与全零结束)将始终等于 num_zeroes * num_ones。这将工作量减半(尽管它仍然是线性的)。

---

从评论来看，似乎有些人没有理解我的回答。这里有一个 Ruby 实现，可以让事情变得更清楚。

def find_min_swaps(arr)
  count_of_ones = 0
  displacement = 0
  arr.each do |v|
    count_of_ones += 1 if v == 1
    displacement += count_of_ones if v == 0
  end

  count_of_zeroes = arr.length - count_of_ones
  reverse_displacement = count_of_ones * count_of_zeroes - displacement
  return [displacement, reverse_displacement].min
end

如果 displacement < reverse_displacement，则零在左边结束，如果它们相等，或者如果 displacement > reverse_displacement，则在右边。