二进制数组的最小相邻交换数 [英] Minimum number of adjacent swaps of binary array

问题描述

给出一个二进制数组，找到将1和0分组所需的最小相邻交换数.

Given a binary array, find the number of minimum adjacent swaps needed to group 1's and 0's.

示例:

Input : 0,1,0,1 (array with 0 based index)
Swaps needed : 0,1,0,1 -> 0,0,1,1 (1 swap from index 1 to index 2)

Solution : 1

示例:

Input : 1,0,1,0,0,0,0,1
Swaps needed : 
1,0,1,0,0,0,0,1 -> 1,1,0,0,0,0,0,1 -> 1,1,0,0,0,0,1,0 -> 1,1,0,0,0,1,0,0 -> 1,1,0,0,1,0,0,0 -> 1,1,0,1,0,0,0,0 -> 1,1,1,0,0,0,0,0

Total 6 swaps so the solution is 6.

1和0可以位于开头或结尾，但它们应位于单个位置，即开头或结尾.

The 1's and 0's can be positioned at the beginning or end but they should be at a single place i.e. either begin or end.

针对此要求，我提出了以下逻辑.我在hackerrank中尝试了此操作，但由于一个隐藏的测试用例而失败，并由于我的代码中嵌套了循环，因此给出了3个测试用例的超时时间.

I have come up with below logic for this requirement. I tried this in a hackerrank, it failed for a single hidden test case and gave timeout for 3 test cases as I have nested loops in my code.

static int countSwaps(List<Integer> list) {
    int temp;
    int swaps = 0;
    int n = list.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if ((list.get(j) == 0) && (list.get(j + 1) == 1)) {
                temp = list.get(j);
                list.set(j, list.get(j + 1));
                list.set(j + 1, temp);
                swaps++;
            }
        }
    }

    return swaps;
}

解决此程序的更好方法是什么?

What is a better approach to solving this program?

我已经看过这篇文章

I have already gone through this post Given an array of 0 and 1, find minimum no. of swaps to bring all 1s together (only adjacent swaps allowed) but the answers are not giving correct output.

推荐答案

建立在 answer by Gene 的基础上，修复了编译问题错误并支持将1移到左侧(开始)或将它们移到右侧(结束)，也就是将0移到左侧:

Building on answer by Gene, fixing the compile error and supporting moving 1's to the left (to the beginning) or moving them to the right (to the end), aka moving 0's to the left:

static int countSwaps(int... a) {
    int n0 = 0, i0 = 0, n1 = 0, i1 = 0;
    for (int p = 0; p < a.length; ++p) {
        if (a[p] == 0)
            n0 += p - i0++; // No. of steps to move the 0 to the left
        else
            n1 += p - i1++; // No. of steps to move the 1 to the left
    }
    return Math.min(n0, n1); // Choose lowest no. of steps
}

测试

System.out.println(countSwaps(0,1,0,1));
System.out.println(countSwaps(1,0,1,0,0,0,0,1));
System.out.println(countSwaps(1,0,0,0,0,1,0,1));

输出

1
6
6

这篇关于二进制数组的最小相邻交换数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！