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

Question

给定一个二进制数组，找出将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

例子：

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

更好的解决这个程序的方法是什么？

我已经查看了这篇文章给定一个由0和1组成的数组，找到将所有1相邻交换移动的最小次数但是答案没有给出正确的输出。

- learner

---

超时的原因是因为您实际上正在手动执行交换操作，这是O(n^2)。有一种数学方法可以计算交换次数，而无需实际执行操作。不幸的是，我暂时不知道该函数，但是这个链接可以解决它。这不是O(n^2)，而是O(2n)->O(n)。 - Compass

@Compass，我看到链接是关于“排序二进制数组”的，所以它总是试图将0放在第一位。但在我的情况下，第一位可以被0或1占据。 - learner

有一种方法可以确定排序的方式，但您也可以在O(4n) -> O(n)执行两种排序，并选择较低的价值，直到您找出那个公式。非常确定它只是计算哪一侧需要移动更多的数字。 - Compass

Answer 1

在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

- Andreas

Answer 2

为了将所有的1移至左侧，设p(i)为从左到右第i个1的位置。第i个1最终需要移动到位置i，这将需要p(i)-i次交换。只需将所有i的此数量加起来即可。

int countSwaps(int [] a) {
  int n = 0, i = 0;
  for (int p = 0; p < a.length; ++p)
    if (a[p] == 1) {
      n += p - i;
      ++i;
    }
  return n;
}

向右移动是对称的。进行类似的计算并取最小值。

- Gene

---

谢谢，我无法理解提供的解释，请问您可以解释一下这个逻辑是如何工作的吗？ - learner

那很好，但它无法编译。 - Andreas

这很不错，但只是挑战的一半。“1和0可以在开头或结尾” 例如，输入1,0,1,0,0,0,0,1 返回 6，但输入 1,0,0,0,0,1,0,1 返回 9，而真实答案也是6，因为您只是将1向右移动而不是向左移动以获得有效结果。 - Andreas

@Gene，根据我的理解，这个逻辑总是把“1”放在开头，但在我的情况下它们也可以保留在结尾。 - learner

@learner 抱歉，我错过了关于开头或结尾的部分。相同的想法适用。只需计算两者并像Andreas一样取最小值即可。 - Gene

Answer 3

这是我的解决方案（Java）：

public static int minSwaps(int[] arr) {
    int min_swaps1 = 0;
    int zero_counts = 0;
    int min_swaps2 = 0;
    int one_counts = 0;

    for (int j : arr) {
        if (j == 0) {
            zero_counts++;
            min_swaps2 += one_counts;
        } else {
            one_counts++;
            min_swaps1 += zero_counts;
        }
    }

    return Math.min(min_swaps1, min_swaps2);
}

- Rainfall

---

问题是关于Java，而不是Python。 - pzaenger