这个Java代码片段如何"工作"？

Question

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

我用调试器逐步完成了这段代码,但我仍然不明白它为什么会这样.有人可以带我走过吗？

Answer 1

让我们试一试看看发生了什么.假设我们有以下数组:

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

请注意,以这种方式观看时,"倒计时"似乎非常明显.