这个问题被称为荷兰国旗问题

图片说明

解题思路:利用三个指针p0, curr, p2,其中p0指向0的右边界,p2指向2的左边界,curr指向当前元素。整个过程确保了[0,p0)的区间都是1,(p2, n-1]的区间都是2。

完整过程:

  1. 将p0初始化为0,curr初始化为0,p2初始化为n-1
  2. 如果curr <= p2:
    1. 如果A[curr]==0,交换curr和p0,将curr和p0都右移
    2. 如果A[curr]==2,交换curr和p2,将p2左移(curr不动)
    3. 如果A[curr]==1,将curr右移

代码如下:

//
// Created by jt on 2020/9/24.
//
#include <algorithm>
using namespace std;

class Solution {
public:
    void sortColors(int A[], int n) {
        int p0 = 0, curr = 0, p2 = n-1;
        while (curr <= p2) {
            if (A[curr] == 0) {
                swap(A[curr], A[p0]);
                ++curr;
                ++p0;
            } else if (A[curr] == 2) {
                swap(A[curr], A[p2]);
                --p2;
            } else ++curr;
        }
    }
};