📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft : Sort 只含0,1,2三个元素的数组

 
🔗
shyJohnnie 2013-8-29 13:50:25 | 只看该作者
全局:
本帖最后由 shyJohnnie 于 2013-8-29 13:52 编辑

三色旗排序问题啊!
遍历一趟即可。
回复

使用道具 举报

🔗
Linzertorte 2013-11-30 11:36:01 | 只看该作者
全局:
本帖最后由 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]);

         }
    }
};
回复

使用道具 举报

🔗
readman 2013-11-30 12:01:09 | 只看该作者
全局:
这题最近各大面试都有..要刷熟悉啊...
回复

使用道具 举报

🔗
GTea 2013-12-1 02:55:01 | 只看该作者
全局:
用quick partition.
回复

使用道具 举报

🔗
marine 2013-12-1 23:13:59 | 只看该作者
全局:
pcoat 发表于 2011-4-28 12:07
既然是排序, 那么肯定0是在最前面, 2是在最后面, 于是只要扫描, 碰到0就和从前开始第一个不为零 ...

嗯,要多设几个指针,指向第一个不为零的数和第一个2。
回复

使用道具 举报

🔗
letmindfly 2013-12-10 04:17:27 | 只看该作者
全局:
我想到的是
快排的变种,用1来partition,<1是0,>1是2. 或者直接用第一个数字做分区,以免碰到没有1的情况。
回复

使用道具 举报

🔗
twfx1123 2013-12-10 11:44:52 | 只看该作者
回复

使用道具 举报

🔗
lautsie 2013-12-10 23:29:57 | 只看该作者
全局:
荷兰旗算法。。。。。。
回复

使用道具 举报

🔗
jason_bourne888 2013-12-11 00:00:57 | 只看该作者
全局:
three way partition
回复

使用道具 举报

🔗
muzac 2013-12-11 18:22:50 | 只看该作者
全局:
这个问题有意思
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表