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

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

 
🔗
CStick75 2012-9-6 19:24:03 | 只看该作者
全局:
或者记录一下1和2的分界点2和3的分界点 然后新来一个就swap就好了 ……最多也就会影响3个元素还是O(n)
回复

使用道具 举报

🔗
sing1ee 2012-9-30 10:39:41 | 只看该作者
全局:
8,9方法都不错,都是快排partition的延伸。15楼的方法牛啊,太取巧了。
回复

使用道具 举报

🔗
chivalry 2012-11-17 20:11:50 | 只看该作者
全局:
应该就是荷兰旗问题的变种
回复

使用道具 举报

🔗
bainikolaus 2012-11-28 03:59:45 | 只看该作者
全局:
我才知道那叫bit map。。。
回复

使用道具 举报

🔗
gongluan 2012-11-30 23:19:20 | 只看该作者
全局:
本帖最后由 gongluan 于 2012-12-1 16:13 编辑

用 3-Way Partitioning 算法解决,只需要扫描一遍元素,时间复杂度 O(n),代码如下

  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <iterator>
  5. #include <algorithm>

  6. using namespace std;

  7. /*
  8. * 3-Way Partitionion Algorithm
  9. *
  10. * See the following materials for more information.
  11. *
  12. *     http://en.wikipedia.org/wiki/Dutch_national_flag_problem
  13. *     http://www.sorting-algorithms.com/quick-sort-3-way
  14. *     Algorithms, 4th Edition, by Robert Sedgewick & Kevin Wayne, p298
  15. */
  16. template <typename BidirectionalIterator>
  17. pair<BidirectionalIterator, BidirectionalIterator>
  18. three_way_partition(BidirectionalIterator first, BidirectionalIterator last)
  19. {
  20.     if (first == last)
  21.         return make_pair(first, first);
  22.     /*
  23.      * +---+---------+---------+---------+---------+
  24.      * |   |    <    |    =    |    ?    |    >    |
  25.      * +---+---------+---------+---------+---------+
  26.      *   ^            ^         ^         ^
  27.      *   |            |         |         |
  28.      * pivot          lt      iter       gt
  29.      */
  30.     BidirectionalIterator pivot = first;
  31.     BidirectionalIterator lt    = ++first;
  32.     BidirectionalIterator iter  = lt;
  33.     BidirectionalIterator gt    = last;

  34.     // Loop through the list and move each element to the right part
  35.     // according to its value compared to the pivot element.
  36.     while (iter != gt) {
  37.         if (*iter < *pivot)         // less than pivot, move left
  38.             swap(*iter++, *lt++);
  39.         else if (*iter > *pivot)    // greater than pivot, move right
  40.             swap(*iter, *--gt);
  41.         else                        // equal to pivot, leave it there
  42.             ++iter;
  43.     }

  44.     // Move the pivot element to the right position
  45.     swap(*pivot, *--lt);

  46.     // Return a pair of iterators pointing to the middle part of the list
  47.     return make_pair(lt, iter);
  48. }

  49. int main()
  50. {
  51.     // 初始时往 vector 里放入一个 1,作为 pivot element
  52.     // vector<int> vec(1, 1);
  53.     list<int> lst(1, 1);

  54.     // 然后往 vector 里面填充 n 个 [0,1,2] 之间的数
  55.     srand(time(NULL));
  56.     const size_t num_elements = 20;
  57.     for (size_t i = 0; i < num_elements; ++i)
  58.         lst.push_back(rand() % 3);

  59.     // 执行 3-way-partion
  60.     three_way_partition(lst.begin(), lst.end());

  61.     // 输出结果
  62.     copy(lst.begin(), lst.end(), ostream_iterator<int>(cout, "  "));
  63.     cout << endl;
  64.     return 0;
  65. }
复制代码
回复

使用道具 举报

🔗
divengence 2012-12-5 23:38:24 | 只看该作者
全局:
wwwyhx 发表于 2011-4-27 18:35
bit map 就是记下各个数重复了多少次的那种类似方法。
比如给一百万个数值从0到100的整数排序,我们就 ...

bit map 也就是bucket sort吧
回复

使用道具 举报

🔗
wvivianjia 2012-12-6 21:57:05 | 只看该作者
全局:
这个题l就是leetcode上的sorting colors....设两个变量,一个从头,一个从后面。。。0往前面存,2往后面,中间剩下1...
回复

使用道具 举报

🔗
zxzxy1988 2012-12-19 23:14:38 | 只看该作者
全局:
wwwyhx 发表于 2011-4-27 18:35
bit map 就是记下各个数重复了多少次的那种类似方法。
比如给一百万个数值从0到100的整数排序,我们就 ...

LZ,这个叫做Bit map?我理解叫做hash,只是hash函数简单了而已。
在网络编程中,我们常常把bitmap这么理解:每个bit代表一个开关量。比如一个交换机有64个端口,那么就定义一个8Bytes的东东(比如数组,或者32bit 机器上的long ),然后其中的每一bit代表一个端口~
回复

使用道具 举报

🔗
zxzxy1988 2012-12-19 23:20:19 | 只看该作者
全局:
darksteel 发表于 2011-5-3 11:01
回复 25# ljfljf2006
不错!其实和快排的pivot划分过程本质上很像,只不过一次用两个pivot把数组划分成三 ...

是的!这个一下子道出了算法的实质!
回复

使用道具 举报

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

本版积分规则

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