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,7，-5 交换为 -5,1,7

然后

-5,1,7,9,-12 交换为 -5,-12,1,7,9

目测时间复杂度是o(n^2)

但是可以用递归将时间复杂度降维nlogn

http://haixiaoyang.wordpress.com/?s=Rearrange

有空可以研究下

//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. do it in-place //e.g. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15//When considering optimization from O(n^2) to O(nlogn),use divided & conquer void swapRange(int a[], int nBeg, int nEnd) {assert(a && nBeg <= nEnd);while (nBeg < nEnd)swap(a[nBeg++], a[nEnd--]); }//solution: //e.g. in any stage: ---- "+++ --" ++++, reverse middle part // ==> ---- "--" "+++" ++++, reverse middle 2 parts seperatly to keep "stable" void ReArrange(int a[], int n) {assert(a && n > 0);if (n <= 1) return;ReArrange(a, n/2);ReArrange(a + n/2, n - n/2); //pitfall, notice both parametersint nLft = 0;while (a[nLft] < 0) nLft++;int nRgt = n-1;while (a[nRgt] >= 0)nRgt--;//Very important, no need to swap under this situation, returnif (nRgt <= nLft) return; swapRange(a, nLft, nRgt);int nBegRgt = nLft;while (a[nBegRgt] < 0) //no need to use "&& nBegRgt < n"nBegRgt++;swapRange(a, nLft, nBegRgt-1);swapRange(a, nBegRgt, nRgt); }

总结

以上是生活随笔为你收集整理的Rearrange an array of positive and negative integers的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。