查看: 2484|回复: 13
收起左侧

Microsoft : Rearrange an array of positive and negative integers,

|只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:Microsoft : 一个栈实现队列
下一篇:Amazon : Find a[i] == i
BillyFan 2011-6-9 21:47:21 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (39)
 
 
2% (1)    👎

  1. 循环原数组,将负数放入“负数数组”,将正数放入“正数数组”
  2. 然后返回 “负数数组” + “正数数组”
  3. <?php
  4. function arr_special_sort($arrInput){
  5.         $arrNeg = array();
  6.         $arrPos = array();
  7.         for($i = 0; $i < count($arrInput); $i++){
  8.                 ($arrInput[$i] < 0) ? array_push($arrNeg,$arrInput[$i]) : array_push($arrPos,$arrInput[$i]) ;
  9.         }
  10.         return array_merge($arrNeg, $arrPos);
  11. }
  12. ?>
复制代码
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-6-11 11:55:07 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

lambda2fei 2012-9-4 17:21:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
wwwyhx 发表于 2011-6-11 11:55
这题的要求因该是”in place rearrange“,
用merge sort 的逻辑可以做到。负数放左,正数方右

正解应该是用0作为pivot应用一次快排的partition过程
回复

使用道具 举报

ryancooper 2012-9-4 18:19:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (35)
 
 
7% (3)    👎
lz你在题目里忘写了in place的要求。如果是in place,那么就用向lz说的用mergesort的逻辑来写;如果不是in place,那么一个O(n)的算法就可以搞定了
回复

使用道具 举报

BinaryWitch 2012-9-4 21:03:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (27)
 
 
6% (2)    👎
回复

使用道具 举报

CStick75 2012-9-6 17:15:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
void partition(int* arr,int N)
{
     int l,r;
     for(l = r = 0 ; r < N ; r ++) if(arr[r]<0) swap(arr[l++],arr[r]);
}
回复

使用道具 举报

BinaryWitch 2012-9-10 13:09:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (27)
 
 
6% (2)    👎
lambda2fei 发表于 2012-9-4 17:21
正解应该是用0作为pivot应用一次快排的partition过程

如果是说 7 楼那样的做法没有注意楼主强调的 BUT... 哦
回复

使用道具 举报

BinaryWitch 2012-9-10 13:12:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (27)
 
 
6% (2)    👎
CStick75 发表于 2012-9-6 17:15
void partition(int* arr,int N)
{
     int l,r;

比如 {3, -1, 4, -2} 这样会改变 3 和 4 在原数组出现次序
回复

使用道具 举报

lambda2fei 2012-9-10 13:19:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
BinaryWitch 发表于 2012-9-10 13:09
如果是说 7 楼那样的做法没有注意楼主强调的 BUT... 哦

汗。。。还有个BUT没看到。。。。那不能快排了。。用归并吧,stl源码的归并排有个参数是可用buffer的大小,如果buffer是O(n),那复杂度就是O(n),否则若buffer是O(1)则好像是O(nlogn)的。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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