活跃农民
- 积分
- 352
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2012-3-1
- 最后登录
- 1970-1-1
|
本帖最后由 Linzertorte 于 2013-11-30 11:39 编辑
longsail 发表于 2013-7-21 14:08 ![]()
利用快速排序 partition 两遍即可 复杂度0(n)
开始我也是分别取0,1为pivots做的partition,不过这个事实上是two pass.了吧
然后我设置了两个标记。one pass就过了
http://oj.leetcode.com/problems/sort-colors/
这是two pass的代码
class Solution {
public:
void sortColors(int A[], int n) {
int pivot=1;
int i,j;
i=-1;
for(j=0;j<n;j++)
if(A[j]<pivot) swap(A[++i],A[j]);
pivot=2;
for(j=i+1;j<n;j++)
if(A[j]<pivot) swap(A[++i],A[j]);
}
};
然后下面是one-pass的代码,debug了半小时
class Solution {
public:
void sortColors(int A[], int n) {
int pivot=1;
int i,j,k;
i=-1,j=-2;
for(k=0;k<n;k++)
if(A[k]<pivot){
if(j<i) swap(A[k],A[++i]),j++;
else{
swap(A[k],A[++j]);
swap(A[i++],A[j]);
}
}else if(A[k]==pivot) {
if(j<i)j=i,i++;
swap(A[k],A[++j]);
}
}
};
|
|