题目

解题思路

本题是经典的【荷兰国旗问题】，最好使用双指针法解决。

已知0，1，2分别表示红、白、蓝。我们设一个指针P0专门用来交换0，P1专门用来交换1。

初始的时候，两个指针都从数组头开始。

遍历过程，如果遇到1，那么和P1指针位置的数交换，并将P1右移；同理，遇到0就和P0指针位置的数交换，但是我们需要注意如果P0<P1，我们已经将一些1换到了头部位置，这个时候会把1换到末尾去（可以打断点走一遍流程），所以我们需要判断如果P0<P1，我们交换完0后，需要把交换出去的那个1交换回来。

代码

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }
}