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

三分数组

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
数组分成三部分,< val, = val, > val

上一篇:Google : 找出单词排序规律
下一篇:特殊数组排序
🔗
xiayuan0623 2011-9-24 02:42:12 | 只看该作者
全局:
本帖最后由 xiayuan0623 于 2011-9-24 03:03 编辑

Once wrote a very similar one before:

Given an unsorted array and two integers b and c(c>b). You need to make the array into 3 partitions, which are “integers less than b”, “integers between b and c”, and “integers greater than c”.

Constraints: o(n) time complexity, o(1) space complexity

int partition(int *a, int size, int b, int c) {
    int p1=0;
    int p2=size-1;
    for (int i=p1;i<=p2;)
    {
        if (a < b)
        {
            int temp=a[p1];
            a[p1]=a[i];
            a[i]=temp;
            p1++;
            i++;
        }
        else if ( a[i] > c)
        {
            int temp=a[p2];
            a[p2]=a[i];
            a[i]=temp;
            p2--;   
        }
        else
        {
           i++;
        }
        
    }
}
[/i][/i][/i][/i][/i]
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-9-24 05:28:41 | 只看该作者
全局:
二分的思想,逻辑上也说不明白,下面是代码

  1. void ThreeWayPartition(int a[], int n, int x)
  2. {
  3.         assert(a && n > 0);

  4.         int nLft = -1;
  5.         int nRgt = -1;
  6.         int nBeg = 0;
  7.         int nEnd = n-1;

  8.         while (nBeg <= nEnd)
  9.         {
  10.                 if (x == a[nBeg] && -1 == nLft)
  11.                         nLft = nBeg;
  12.                 if (x == a[nEnd] && -1 == nRgt)
  13.                         nRgt = nEnd;

  14.                 if (a[nBeg] <= x)
  15.                 {
  16.                         if (-1 != nLft && a[nBeg] != x)
  17.                         {
  18.                                 swap(a[nLft], a[nBeg]);
  19.                                 nLft++;
  20.                         }

  21.                         nBeg++;
  22.                 }
  23.                 else if (a[nEnd] >= x)
  24.                 {
  25.                         if (-1 != nRgt && a[nEnd] != x)
  26.                         {
  27.                                 swap(a[nRgt], a[nEnd]);
  28.                                 nRgt--;
  29.                         }

  30.                         nEnd--;
  31.                 }
  32.                 else
  33.                         swap(a[nBeg], a[nEnd]);
  34.         }
  35. }
复制代码
回复

使用道具 举报

🔗
xiayuan0623 2011-9-24 08:45:06 | 只看该作者
全局:
楼主这些题都是哪里来的...都貌似是很经典的面试题啊...

下周两个面试..正好需要临阵磨枪...=_=
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-9-24 09:46:26 | 只看该作者
全局:
楼主这些题都是哪里来的...都貌似是很经典的面试题啊...

下周两个面试..正好需要临阵磨枪...=_=
xiayuan0623 发表于 2011-9-24 08:45


mitbbs上的, 自己找自己做啊
回复

使用道具 举报

🔗
Imbalism 2011-9-24 13:29:42 | 只看该作者
全局:
本帖最后由 Imbalism 于 2011-9-24 13:30 编辑
  1. template <typename Iterator, typename T>
  2. void triblecut(Iterator first, Iterator last, const T& value){
  3.         if(first == last)
  4.                 return;
  5.         Iterator i = first - 1;
  6.         Iterator j = last;
  7.         while(first != j){
  8.                 if(*first > value)
  9.                         first++;
  10.                 else if(*first < value)
  11.                 {
  12.                         ++i;
  13.                         swap(*i, *first);
  14.                         first++;
  15.                 }else{
  16.                         --j;
  17.                         swap(*j, *first);
  18.                 }
  19.         }
  20. }
复制代码

快速排序版本
回复

使用道具 举报

🔗
ilhrx 2011-10-3 13:52:05 | 只看该作者
全局:
感觉就是手动做两遍快排。。。。
先定好b的位置。。。。然后定c的位置
默认升序。
  1. x=b;
  2. Head=1; Tail=n;
  3. while(Head<Tail){
  4.      while(a[Head]<x && Head<Tail)  Head++;
  5.      while(a[Tail]>x && Head<Tail)  Tail--;
  6.      if (Head<Tail) swap(&a[Head],&a[Tail]);
  7.     }
  8.    //now Head=Tail
  9.   if (a[Tail]>x)  then  Position_of_b =Tail+1
  10.                       else   Position_of_b is Tail-1
  11. x=c;
  12. Head=Position_of_b+1; Tail=n;
  13. while(Head<Tail){
  14.      while(a[Head]<x && Head<Tail)  Head++;
  15.      while(a[Tail]>x && Head<Tail)  Tail--;
  16.      if (Head<Tail) swap(&a[Head],&a[Tail]);
  17.     }
  18.    //now Head=Tail
  19.   if (a[Tail]>x)  then  Position_of_c = Tail+1
  20.                       else   Position_of_c = Tail-1
  21. }
复制代码
回复

使用道具 举报

🔗
chenyongsuda 2012-5-22 14:55:51 | 只看该作者
全局:
这个应该是荷兰旗问题  3 way partition
回复

使用道具 举报

🔗
mimighost007 2012-5-22 15:00:44 | 只看该作者
全局:
快排的思想么~~~~~
回复

使用道具 举报

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

本版积分规则

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