Rearrange an array of positive and negative integers

本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---