首页 > 代码库 > 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++; } } } } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。