如果给定一个1和0的数组，那么有什么好算法可以显示将所有1分组在一起所需的最小相邻交换数。1不需要在数组中的任何特定位置进行分组。它们只需要分组在任何提供最小数量相邻掉期的地方。
例如，如果数组看起来像这样。。。
1,0,0,1,1,0,1
相邻交换的最小数量为3，因为您将以索引4为中心并进行以下交换：
-
交换索引0和1，结果是：
0,1,0,1,1,0,1 -
交换索引1和2，结果是：
0,0,1,1,1,0,1 -
交换指数5和6，结果是：
0,0,1,1,1,1,0
有人有一个很好的算法来找到1和0的任何数组的最小相邻交换数吗？
更新：
该算法仅通过获得所有索引为1的数组来确定中心。该数组的中心将始终包含中心索引。速度要快得多。
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);
下面是一把小提琴，看看它的作用：
https://jsfiddle.net/3pmwrk0d/6/
这很有趣。谢谢你的提问。
嗨，首先我想建议，对于给定的示例，相邻交换的最小数量应该是2，而不是3。正如将索引0与索引2交换一样。所以从左边换一个，从右边换一个
以下是我的方法来找到最小的交换，以使阵列处于连续1的形式-
步骤1：首先找到连续1的最大数量的中心索引步骤2：解析数组的左侧以进行交换，并以有效的方式计算交换次数（不要进行不必要的交换）步骤3：对右侧阵列执行相同操作第四步：加上双方的计数。
请看一下我基于相同策略的java程序：
`public class MinimumSwap
{
//function to find consecutive number index
public static int[] getMaxConsecutiveIndex(List<Integer> array)
{
int desiredIndex = -1;
int count = 0;
int dupDesiredIndex = -1;
int dupCount = 0;
int i = 0;
while(i < array.size())
{
if(array.get(i) == 0)
{
//pass duplcateIndex value to desiredIndex if count is more
if(dupCount > count)
{
desiredIndex = dupDesiredIndex;
count = dupCount;
}
dupDesiredIndex = -1;
dupCount = 0;
}
else
{
if(dupDesiredIndex == -1)
{
dupDesiredIndex = i;
dupCount = 1;
}
else
{
dupCount++;
}
}
i++;
}
return new int[]{desiredIndex,count};
}
public static int swapCount(List<Integer> array,int startIndex, int endIndex, boolean side)
{
// side == false means 0 at the left
// side == true means 1 at the left
System.out.println("startIndex "+startIndex+" endIndex "+endIndex+" side "+side);
int swapCount = 0;
if(side == false)
{
while(startIndex <= endIndex)
{
if(array.get(endIndex) == 0) // swap from the end only if it is 0
{
//check for first 1 from left to swap
while(array.get(startIndex) == 0 && (startIndex != endIndex))
startIndex++;
if(array.get(startIndex) == 1)
{
// now swap
int temp = array.get(startIndex);
array.set(startIndex, array.get(endIndex));
array.set(endIndex,temp);
swapCount++;
endIndex--;
}
}
endIndex--;
}
}
else
{
while(startIndex <= endIndex)
{
if(array.get(startIndex) == 0) // swap from the starting only if it is 0
{
//check for first 1 from right to swap
while(array.get(endIndex) == 0 && (startIndex != endIndex))
endIndex--;
if(array.get(endIndex) == 1)
{
// now swap
int temp = array.get(startIndex);
array.set(startIndex, array.get(endIndex));
array.set(endIndex,temp);
swapCount++;
startIndex++;
}
}
startIndex++;
}
}
return swapCount;
}
public static void main(String...strings)
{
List<Integer> arr = new ArrayList<Integer>();
int temp[] = {0,1,1,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,0,1};
//int temp[] = {1,0,0,1,1,0,1};
for(int i=0; i<temp.length; i++)
arr.add(temp[i]);
int centerIndex = getMaxConsecutiveIndex(arr)[0];
int consequtivecount = getMaxConsecutiveIndex(arr)[1];
System.out.println("centerIndex "+centerIndex+" consequtivecount "+consequtivecount);
int swapCountLeft = swapCount(arr,0, centerIndex-1, false);
int swapCountRight = swapCount(arr,centerIndex+consequtivecount, arr.size()-1, true);
System.out.println("total swap count "+swapCountLeft+" :: "+swapCountRight);
System.out.println("array after swapping "+arr);
}
}`
我对表现不是很确定。但据我所知，这不应该是低效的。如果有人发现任何性能问题，请告诉我：）
方法：这可以通过在每1的右侧找到零的数量并将它们相加来实现。为了对数组进行排序，每个数组都必须执行一个交换操作，每个零都在其右侧。
因此，数组中特定1的交换操作总数是其右侧的零数。找出每一个的右侧零的数量，即掉期的数量，并将它们全部相加，以获得掉期的总数。
//Java代码，用于查找对二进制数组进行排序的最小交换次数
class MinimumNumberOfSwapsNeeded {
static int findMinSwaps(int arr[], int n)
{
// Array to store count of zeroes
int noOfZeroes[] = new int[n];
int i, count = 0;
// Count number of zeroes
// on right side of every one.
noOfZeroes[n - 1] = 1 - arr[n - 1];
for (i = n - 2; i >= 0; i--)
{
noOfZeroes[i] = noOfZeroes[i + 1];
if (arr[i] == 0)
noOfZeroes[i]++;
}
// Count total number of swaps by adding number
// of zeroes on right side of every one.
for (i = 0; i < n; i++)
{
if (arr[i] == 1)
count += noOfZeroes[i];
}
return count;
}
// Driver Code
public static void main(String args[])
{
int ar[] = { 0, 0, 1, 0, 1, 0, 1, 1 };
System.out.println(findMinSwaps(ar, ar.length));
}
}
**对0和1的数组进行分组，使最小交换可以在O（2*n）~O（n）复杂度中计算。**
package com.segregate.array;
import java.util.ArrayList;
import java.util.List;
public class ArraySegregation {
public static void main(String[] args) {
List<Integer> arr = new ArrayList<>();
/*
*
* List -> low high [1 1 0 0 1 0] -> [ 000111] or [111000]
*
* 1 1 0 0 1 0 -> 000111
*/
arr.add(0);
arr.add(0);
arr.add(0);
arr.add(1);
arr.add(1);
arr.add(0);
arr.add(1);
arr.add(0);
arr.add(0);
List<Integer> arr1 = new ArrayList<>(arr);
int low = 0, high = arr.size() - 1;
int counter1 = 0, counter2 = 0;
// case for swaps such that all 0 in the left side.
while (low < high) {
switch (arr.get(low)) {
case 0:
while (arr.get(low) == 0)
low++;
break;
case 1:
while (arr.get(high) == 1)
high--;
swap(low, high, arr);
counter1++;
high--;
low++;
break;
}
}
// case for swaps such that all 0 in the right side.
/*
* [1 1 0 0 1 0] -> 11 1 0 0 0
*
*
*/
low=0;high = arr1.size() - 1;
while (low < high) {
switch (arr1.get(low)) {
case 0:
while (arr1.get(high) == 0)
high--;
swap(low, high, arr1);
counter2++;
high--;
low++;
break;
case 1:
while (arr1.get(low) == 1)
low++;
break;
}
}
int count = (counter1 > counter2) ? counter2 : counter1;
System.out.println(count);
}
private static void swap(int low, int high, List<Integer> arr) {
int temp1 = 0;
temp1 = arr.get(low);// 1
arr.remove(low);
arr.add(low, arr.get(high-1));
arr.remove(high-1);
arr.add(high, temp1);
}
}
这里有一个简单但不太聪明的算法，它将对[0255]范围内的任何输入执行穷举搜索。
-
输入：
- 二进制字符串
-
输出：
- 最佳步数
- 最优解的数目
- 一个详细的例子
var transition = [],
isSolution = [];
function init() {
var msk = [ 3, 6, 12, 24, 48, 96, 192 ],
i, j, n, x, cnt, lsb, msb, sz = [];
for(i = 0; i < 0x100; i++) {
for(n = cnt = msb = 0, lsb = 8; n < 8; n++) {
if(i & (1 << n)) {
cnt++;
lsb = Math.min(lsb, n);
msb = Math.max(msb, n);
}
}
sz[i] = msb - lsb;
isSolution[i] = (sz[i] == cnt - 1);
}
for(i = 0; i < 0x100; i++) {
for(j = 0, transition[i] = []; j < 0x100; j++) {
x = i ^ j;
if(msk.indexOf(x) != -1 && (x & i) != x && (x & j) != x && sz[j] <= sz[i]) {
transition[i].push(j);
}
}
}
}
function solve() {
var x = parseInt(document.getElementById('bin').value, 2),
path = [ x ],
list = [],
i, min, sol = [], res = [];
recurse(x, path, list);
for(i in list) {
if(min === undefined || list[i].length <= min) {
min = list[i].length;
(sol[min] = (sol[min] || [])).push(list[i]);
}
}
console.log('Optimal length: ' + (min - 1) + ' step(s)');
console.log('Number of optimal solutions: ' + sol[min].length);
console.log('Example:');
for(i in sol[min][0]) {
res.push(('0000000' + sol[min][0][i].toString(2)).substr(-8, 8));
}
console.log(res.join(' -> '));
}
function recurse(x, path, list) {
if(isSolution[x]) {
list.push(path);
return;
}
for(i in transition[x]) {
if(path.indexOf(y = transition[x][i]) == -1) {
recurse(y, path.slice().concat(y), list);
}
}
}
init();<input id="bin" maxlength="8" placeholder="enter binary string">
<button onclick="solve()">solve</button>