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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。