分隔 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 次交换

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

求使所有 0 和所有 1 都在一起所需的最少交换次数

我没有对数组进行排序，我只是试图将所有 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

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