首页 > 代码库 > leetcode第一刷_Sort Colors

leetcode第一刷_Sort Colors

挺有意思的一道题目,属于我之前没有总结到的情况,他在修改数组的时候用到了第三个指针。

如果是两种颜色的话,大家肯定都会做,直接一头一尾两个指针,扫描到不属于自己同类的就互换。这个题有了第三者,怎样来解决这个问题呢?想一下在一个数组中,怎样才能做到线性时间的修改,必须一次性或者常数性的把当前元素替换到他最终应该待的位置,要么复杂就上去了。那当前元素应该呆在那里呢?如果是0的话,应该呆在数组前面都是0的某个地方,如果是2,应该呆在数组后面都是2的地方。那如果是1呢,应该呆在中间,但是0和2最终在哪只有上帝知道,这个中间不好定义。但是头和尾是可以知道的,这个走遍天下都一样,因此我们只能放弃第三者,只考虑两个原配的位置。

原配的位置一定是要有两个指针来保存的,一个在头一个在尾,只有当新的同类加入时,他们才会移动。因此这个题扫描数组的任务必须交给第三个指针,也是这道题的关键。从头开始,如果第三指针遇到的是0,那么应该替换到数组头,并把0号原配的指针往后推进,如果遇到的是2,那么,应该替换到数组尾部,并把2号原配的指针往前推进一个位置,这里要注意,如果替换回来的是0怎么办?只能做二次替换,因为一旦错过了这次机会,这个0就一直呆在小三位置上了。所以就像一开始遇到0一样,把他往前替换。注意到替换到第三指针指向位置的一定是个小三,因为如果是2号原配,早就替换回数组尾部了,第三指针是依次扫过来的嘛。最后,过程中如果遇到的是小三1,那么就直接忽略,因为如果他在不应该待的位置上,总有一天会有原配来把他替换走的,就像在生活中一样。

class Solution {
public:
    void sortColors(int A[], int n) {
        int beg = 0, end = n-1;
        for(int i=0;i<=end;i++){
            if(A[i] == 0){
                if(A[i] != A[beg])
                    swap(A[beg], A[i]);
                ++beg;
            }else if(A[i] == 2){
                while(end>i&&A[end] == 2)
                    --end;
                if(end<=i)  break;
                swap(A[end], A[i]);
                --end;
                if(A[i] == 0){
                    swap(A[beg], A[i]);
                    beg++;
                }
            }
        }
    }
};