给定一个0和1的数组，找到最小值。交换以将所有1组合在一起（仅允许相邻交换） [英] Given an array of 0 and 1, find minimum no. of swaps to bring all 1s together (only adjacent swaps allowed)
问题描述
如果给定一个由1和0组成的数组，那么最好的算法是显示将所有1组合在一起所需的最小相邻交换数。 1不需要在数组中的任何特定位置分组。只要将它们分组在提供最小相邻交换次数的任何位置即可。
If given an array of 1's and 0's, what's good algorithm to show the minimum number of adjacent swaps needed to group all of the 1's together. The 1's don't need to be grouped at any specific place in the array. They just need to be grouped in whatever place provides for the minimum number of adjacent swaps.
例如，如果数组看起来像这样……
For example, if the array looks like this...
1,0,0,1,1,0,1
...相邻交换的最小数量为3，因为您将以索引4为中心并进行以下交换：
...the minimum number of adjacent swaps would be 3, because you'd center on index 4 and do the following swaps:
-
交换索引0和1，得到：
0,1,0,1,1,0,1
交换索引1和2，得到：
0,0,1,1,1,0,1
Swap indices 1 and 2, resulting in:
0,0,1,1,1,0,1
交换索引5和6，得到：
0,0,1,1,1,1,0
Swap indices 5 and 6, resulting in:
0,0,1,1,1,1,0
每个人都有一个很好的算法，可以找到任意数组的最小相邻交换数1和0？
Anyone have a good algorithm for finding the minimum number of adjacent swaps for any array of 1's and 0's?
推荐答案
更新：
算法确定中心通过仅获取所有1的索引数组。该数组的中心将始终保持中心索引。
The algorithm determines center by just getting an array of all indices of 1's. The center of that array will always hold the center index. Much faster.
oneIndices = array of indices of all 1's in the input
middleOfOnesIndices = round(oneIndices.length/2)-1 // index to the center index
minimumSwaps = 0
foreach index i of oneIndices
minimumSwaps += aboluteValue(oneIndices[middleOfOneIndices]-oneIndices[i])-absoluteValue(middleOfOneIndices-i);
在这里看到它的作用很简单：
Here's a fiddle to see it in action:
https://jsfiddle.net/3pmwrk0d/6/
这很有趣。谢谢你的提问。
This was a fun one. Thanks for the question.
这篇关于给定一个0和1的数组，找到最小值。交换以将所有1组合在一起（仅允许相邻交换）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
