如何解决以下编程问题.
有一个数组只包含0s和1s按随机顺序排列.的位置1可以与任何位置被切换0.什么是所需的最小交换数量,以便所有交换1s在一起.
解决这个问题的最佳方法是什么？我甚至无法想出蛮力的方法.
例如,考虑以下数组(索引从0开始)
数组大小14 1 0 0 0 1 0 1 0 1 0 0 0 0 1
第一次传递后0 0 0 0 1 1 1 0 1 0 0 0 0 1(索引0与索引5交换)
第二次传球后0 0 0 0 1 1 1 1 1 0 0 0 0 0(指数7与指数13交换)
需要两次交换才能将所有内容1s整合在一起
首先,计算1s 的数量(让我们称之为k).这可以在O(n)中完成.
接着,通过行走该阵列,并计算后的总和k每个索引元件i之间k和n.这也可以在O(n)中完成,通过使用先前元素的和加上当前值减去位置上的值i-k.
互换的数量等于k-max(sum).
在你的例子中,k是5. k-sums如下:
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组合在一起的s 的运行结束的地方,因为它在k索引块中具有最高的"浓度" .这是您要复制1的位置,您需要复制k-max剩余的1s.