荷兰国旗问题的两种解决方案之间的差异

Question

我对这个问题的解决方案有一些疑问：

https://leetcode.com/problems/sort-colors/description/

1. 为什么从左向右遍历时必须先处理2，再处理0？还有为什么从右向左遍历时一定要先处理0，再处理2？

2. 为什么必须把

   if

   时的

   num[i]==0

   语句改为从右向左遍历时的

   while

   语句？

我想知道这些现象的深层次原因。谢谢你。

从左向右遍历的解法：

class Solution {
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void sortColors(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        // Traverse from left to right.
        for (int i = 0; i < nums.length; i++) {
            // first "2", then "0", the order is irreversible.
            while (i < end && nums[i] == 2) {
                swap(nums, end, i);
                end--;
            }
            if (nums[i] == 0) { // or `while (i > start && nums[i] == 0)`
                swap(nums, start, i);
                start++;
            }
        }
    }
}

从右向左遍历的解法：

class Solution {
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void sortColors(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        // Traverse from right to left.
        for (int i = nums.length - 1; i >= 0; i--) {
            // first "0", then "2", the order is irreversible.
            while (i > start && nums[i] == 0) { // Cannot use `if (nums[i] == 0)`.
                swap(nums, start, i);
                start++;
            }
            while (i < end && nums[i] == 2) {
                swap(nums, end, i);
                end--;
            }
        }
    }
}

Answer 1

因为从左向右遍历时，交换2到最后后，可能会有一个

0

交换过来。这时就需要不断地处理这个0。比如

[2,1,0,0,2]

，交换后就变成了

[0,1,0,2,2]

。那么这个时候就必须对这个

0

进行处理，即swap(nums, 0, 0)。如果先处理0，再处理2，那么交换完

0

后，就不会执行

swap(nums, 0, 0)

操作。

为什么必须执行

swap(nums, 0, 0)

？因为执行完

start++

之后，start就指向了连续0段的下一个位置。这样以后遇到0的时候就可以直接进行一次swap，而不需要使用while循环。 （使用

while

循环是因为交换后，当前元素可能没有改变。因此，

swap

需要在循环中执行。但此时，我们必须交换一个非零元素和一个

 0

，所以只能执行一次。）

从右到左，同样。因此，在解决方案中从右到左，改变

            while (i < end && nums[i] == 2) {

到

            if (nums[i] == 2) {

也是可以的。