首页 > 代码库 > Sort Colors [leetcode] 扫描数组一遍，O(1)空间复杂度的解法
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;回到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)空间复杂度的解法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。