1

Java面试题是：

在不使用临时缓冲区的情况下，将 0 和 1 从数组中分离出来，将所有 0 放在左侧，将 1 放在右侧。将结果打印为字符串。例如，给定 {0,1,1,0,0,1}，输出为“000111”。

答案是：

public class ZeroOneSeparator {

    public static void zeroOneSeparator(int[] inputArr){

        // for each index, store number of 1's up to the index
        for (int i = 1; i < inputArr.length; i++) {
            inputArr[i] = inputArr[i-1] + inputArr[i];  
        }

        // This is the "magical math" block I don't understand.
        // Why does this "work"?
        for (int i = inputArr.length - 1; i > 0; i--) {
            if (inputArr[i] > 0) {
                inputArr[i-1] = inputArr[i] - 1;
                inputArr[i] = 1;
            } else {
                inputArr[i-1] = 0;
            }
        }

        for (int i = 0; i < inputArr.length; i++) {
            System.out.print(inputArr[i]);
        }
    }

    public static void main(String[] args) {
        int[] inputArr1 = {1,0,1,0,1,1};
        ZeroOneSeparator.zeroOneSeparator(inputArr1);
        System.out.println();
        int[] inputArr2 = {1,1,1,0,0,0,0,0,0,1};
        ZeroOneSeparator.zeroOneSeparator(inputArr2);
        int[] inputArr3 = {}; // intentionally empty
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr3);
        int[] inputArr4 = {0,0,0,0,0,0};
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr4);
        int[] inputArr5 = {0,1,0,1,0,1,0,1};
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr5);
        int[] inputArr6 = {1,1,1,1,1,1,0,0,0,0,0};
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr6);
    }
}

我用调试器逐步完成了这段代码，但我仍然不明白它为什么会起作用。有人可以带我过去吗？

4

3 回答 3

7

让我们尝试一个例子来看看发生了什么。假设我们有以下数组：

0 1 1 0 1 1 0 0

第一个循环（如注释所指定）计算到目前为止看到的 1 的总数，其中每个 1 增加计数，每个 0 保持不变。所以对于我们的数组，我们最终得到这个：

0 1 2 2 3 4 4 4

请注意，数组的最后一个元素现在是 4，这是 1 的总数。我们在下一个循环中使用这个事实。

我们从最后一个元素开始，检查它是否大于 0。如果是，则用 1 替换该元素，然后将该计数减 1 并将其分配给前一个元素。我们一直这样做，边走边填 1，直到计数达到 0。此时，我们将遇到的每个元素设置为 0。

这里真正发生的是，一旦我们知道有多少个 1，我们就可以从数组的末尾“倒数”，填充那个数量的 1。此时，我们知道其余元素必须为 0，因此我们可以在该点将其余元素设置为 0。

从视觉上看，它看起来像这样（“当前元素”被 [] 包围）

0 1 2 2 3 4 4 [4] ->
0 1 2 2 3 4 [3] 1 ->
0 1 2 2 3 [2] 1 1 ->
0 1 2 2 [1] 1 1 1 ->
0 1 2 [0] 1 1 1 1 ->
0 1 [0] 0 1 1 1 1 ->
0 [0] 0 0 1 1 1 1 ->
0 0 0 0 1 1 1 1

请注意，以这种方式查看时，“倒计时”似乎非常明显。

于 2012-07-02T03:50:01.360 回答
2

由于您在最后一个索引处的数组中有 1 的计数，因此您只需从后面循环并将其替换为 1。代码中的技巧是，它减少 1 的计数并将其存储在每一步中的前一个数组元素中，以便在下一步中，它知道当前元素是 0 还是 1。它工作得很好即使在所有 1 或几乎所有 1 的情况下（数组中只有一个 0），因为当它修改索引 0 处的元素时，1 的左侧计数正好是正确的数字。

就个人而言，我会记录 1 的计数，得出 0 的计数并使用 2 个循环来打印/设置数组中的数字。

于 2012-07-02T03:46:17.803 回答
1

第一个for 循环计算每个项目左侧有多少个 1。如果输入为{0,1,1,0,0,1}，则作为计数的结果，输入数组变为{0,1,2,2,2,3}。

最后一个索引 3 表示列表中有三个 1。第二个for循环反向遍历列表，并将最后三个项目标记为 1。

于 2012-07-02T03:50:38.730 回答