更新:
该算法通过获取所有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/
这是一个很有趣的问题，感谢提问。
方法： 可以通过找到每个1右侧的零的数量并将它们相加来完成。为了对数组进行排序，每个1始终必须执行与其右侧每个零的交换操作。
因此，数组中特定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));
}
}
你好，首先我想建议你的示例中相邻交换的最小次数应该是2而不是3。只需将索引0与索引2交换即可。因此从左侧进行1次交换，从右侧进行1次交换。
以下是我找到将数组转换为连续1形式的最小交换次数的方法：
步骤1：首先找到最大连续1的中心索引 步骤2：解析左侧数组以进行交换，并以高效的方式计算交换次数（不要不必要地交换） 步骤3：对右侧数组执行相同操作 步骤4：将两侧的计数相加。
请查看基于相同策略的我的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);
}
我对性能不是很确定。但据我所知，它不应该是低效的。如果有人发现任何性能问题，请告诉我 :)
将由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);
}
}
这里有一个简单但不是非常聪明的算法，它将对范围[0, 255]内的任何输入执行穷举搜索。
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>