java - 如何将数组(仅由 1's and 0' 组成)的元素 1 与 0 交换，以便所有 1 都在一起

Question

如何解决以下编程问题。

有一个数组，仅由 0 和 1 组成，且顺序随机。 1的位置可以与0的任意位置互换。最少需要多少次交换才能使所有 1 组合在一起。

解决这个问题的最佳方法是什么？我什至无法想出暴力方法。

例如，考虑以下数组(索引从0开始)

1. 数组大小 14 1 0 0 0 1 0 1 0 1 0 0 0 0 1

2. 第一次传递后0 0 0 0 1 1 1 0 1 0 0 0 0 1(索引 0 与索引 5 交换)

3. 第二遍之后0 0 0 0 1 1 1 1 1 0 0 0 0 0(索引 7 与索引 13 交换)

需要两次交换才能将所有 1 组合在一起

Answer 1

首先，计算 1 的数量(我们称之为 k)。这可以在 O(n) 内完成。

接下来，遍历数组，并计算 k 和 n 之间每个索引 i 的尾随 k 元素的总和。这也可以在 O(n) 内完成，方法是使用前一个元素的总和加上当前值减去位置 i-k 处的值。

交换次数等于k-max(sum)。

在您的示例中，k 为 5。k 和如下:

1 0 0 0 1 0 1 0 1 0 0 0 0 1
- - - - 2 1 2 2 3 2 2 1 1 1

最大总和为3，因此交换次数为5-3=2。

注意:该算法的直观原理很简单:总和最高的位置是组合在一起的 1 运行即将结束的位置，因为它在 k 索引 block 中具有最高的“集中度”。这是您将复制 1 的位置，并且需要复制 k-max 剩余的 1。