首页 > 代码库 > leetcode:Sort Colors
leetcode:Sort Colors
一、 题目
给一个数组包含n个物体,有蓝色、红色和白色三种颜色,把他们分类并按照红、白、蓝的顺序排列,我们用0、1、2来表示红白蓝的颜色
注解:很容易想到遍历两遍数组得到三个数的数目,再覆盖,但是请只遍历一遍数组来解决。
二、 分析
很简单,题目的意思其实就是让对一个数组排序,数组中的元素只有0、1、2,并且要求只能遍历一遍数组,常数空间复杂度。此时我们可以想到借助于快速排序 的partition思想,以1为中间枢纽对数组进行划分,使0在数组的左边,2在数组的右边,1在数组的中间。
[cpp] view plaincopyprint?
- class Solution {
- public:
- void sortColors(int A[], int n) {
- int end = -1;
- int start = n;
- int i=0;
- //end是放0那部分的尾部索引,start是放2那部分的首部索引
- //碰到0放到end+1处,碰到2放到start-1处,碰到1指针直接后移
- while(i<start){
- if(A[i] == 0 && i!=++end)
- swap(A[end],A[i]);
- else if(A[i] == 2 && i!= --start)
- swap(A[start],A[i]);
- else
- i++;
- }
- }
- };
leetcode:Sort Colors
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。