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

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

2024-07-23 19:04:00   220人阅读

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

扫描数组一遍的方法：

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;

回到A中，i=0的时候，nextPos变成了{1, 1, 1}，没有问题，但是A[0]变成2了。所以我们需要将for循环倒过来，使得A[0]仍为0

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

但是这个循环不会正确运行，因为c=2时将A[0]变成2了，c-- < 2，循环结束。所以我们需要用另外一个变量记录下A[i]最初的值，得到最终的程序：

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)空间复杂度的解法


联系
我们