leetcode练习题 sort-colors

解题思路

和荷兰国旗三色排列类似
设置变量head、tail、i(用于遍历数组)
1、若为0，则与A[head]交换，head++、i++
2、若为1，则跳过，0、2首尾确定了，1自然放在中间。
3、若为2，则与A[tail]交换，tail–,此时不能i++，因为数组后半部分还没访问到，交换过来的有可能为0也有可能为2也有可能为1，需要继续判断。

代码

#include<algorithm>
class Solution {
public:void sortColors(int A[], int n) {int head = 0,tail = n - 1,i = 0;while(i <= tail){if(A[i] == 1)i++;else if(A[i] == 0){swap(A[i],A[head]);head++;i++;}else{swap(A[i],A[tail]);tail--;}}}
};