Microsoft : Rearrange an array of positive and negative integers,

Given an array of positive and negative integers, re-arrange it
so that you have postives on one end and negatives on the other,
BUT retain the original order of appearance.
For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15

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

复制代码

这题的要求因该是”in place rearrange“,
用merge sort 的逻辑可以做到。负数放左，正数方右

wwwyhx 发表于 2011-6-11 11:55
这题的要求因该是”in place rearrange“,
用merge sort 的逻辑可以做到。负数放左，正数方右

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

lz你在题目里忘写了in place的要求。如果是in place，那么就用向lz说的用mergesort的逻辑来写；如果不是in place，那么一个O(n)的算法就可以搞定了

这里有详细的解答
http://www.51nod.com/answer/index.html#!answerId=375

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]);
}

lambda2fei 发表于 2012-9-4 17:21
正解应该是用0作为pivot应用一次快排的partition过程

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

CStick75 发表于 2012-9-6 17:15
void partition(int* arr,int N)
{
     int l,r;

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

BinaryWitch 发表于 2012-9-10 13:09
如果是说 7 楼那样的做法没有注意楼主强调的 BUT... 哦

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