Sort Colors [leetcode] 扫描数组一遍，O(1)空间复杂度的解法

扫描数组两遍的方法是：第一遍计算有每个颜色有多少个，第二遍再将所有颜色赋回数组

扫描数组一遍的方法：

nextPos数组中记录三种颜色的下一个位置

考虑A={0，2，1，1，0}时我们应该如何更新nextPos

初始：nextPos = {0，0，0}

第一个颜色是0，所以nextPos[0] = 1。A={0...} 但是由于1和2必须在0的后面，所以nextPos[1], nextPos[2]均为1

第二个颜色是2，所以nextPos[2] = 2。A={0, 2...} 1和0均在2的前面，所以不用更新其他值

第三个颜色是1，nextPos[1]++，值为2。同时应把2往后挪一位，A为{0, 1, 2...}。nextPos[2] = 3。

第四个颜色是1，nextPos[1]++，值为3。2还要再往后挪一位，nextPos[2] = 4。

最后一个颜色是0，所以A[1]=0，其他所有颜色均需往后挪一位，A[3] = 1, A[4] = 2。nextPos[1]=4, nextPos[2]=5。

观察以后可以发现当前颜色color = A[i]，我们需要将所有大于color的颜色均往后挪，同时对应的nextPos++

可以在一句话里写完：

for (int c = A[i]; c < 3; c++)
      A[nextPos[c]++] = c;

for (int c = 2; c >= A[i]; c--)
      A[nextPos[c]++] = c;

void sortColors(int A[], int n) {
    int nextPos[3] = {0};
    for (int i = 0; i < n; i++)
    {
        int color = A[i];
        for (int c = 2; c >= color; c--)
            A[nextPos[c]++] = c;
    }
}

Sort Colors [leetcode] 扫描数组一遍，O(1)空间复杂度的解法

原文：http://blog.csdn.net/peerlessbloom/article/details/39476031