java - 二进制数组的最小相邻交换数

给定一个二进制数组，求出1和0组所需的最小相邻交换数。
例子：

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

Exmaple公司：

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可以放在开头或结尾，但它们应该放在一个地方，即开头或结尾。
我为这个要求提出了以下逻辑。我在一个hackerrank中尝试了这个方法，但是对于一个隐藏的测试用例失败了，并且由于我在代码中嵌套了循环，所以给了3个测试用例超时。

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;
}

解决这个问题的更好方法是什么？
我已经看过这篇文章了，但是答案没有给出正确的答案。

最佳答案

建立在answer by Gene上，修正编译错误并支持移动1的左边（到开始）或移动到右边（到最后），移动0到左边：

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

关于java - 二进制数组的最小相邻交换数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56878798/