这个问题被称为荷兰国旗问题
:
解题思路:利用三个指针p0, curr, p2
,其中p0指向0的右边界,p2指向2的左边界,curr指向当前元素。整个过程确保了[0,p0)
的区间都是1,(p2, n-1]
的区间都是2。
完整过程:
- 将p0初始化为0,curr初始化为0,p2初始化为n-1
- 如果
curr <= p2
:- 如果
A[curr]==0
,交换curr和p0,将curr和p0都右移 - 如果
A[curr]==2
,交换curr和p2,将p2左移(curr不动) - 如果
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; } } };