mysileng

第二十七章：不改变正负数之间相对顺序重新排列数组.时间O(N)，空间O(1)

前言

    在这篇文章：九月腾讯，创新工场，淘宝等公司最新面试十三题的第5题(一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来的正负数之间相对顺序)，自从去年九月收录了此题至今，一直未曾看到令人满意的答案，为何呢?

    因为一般达不到题目所要求的：时间复杂度O(N),空间O(1)，且保证原来正负数之间的相对位置不变。本编程艺术系列第27章就来阐述这个问题，若有任何漏洞，欢迎随时不吝指正。谢谢。

重新排列使负数排在正数前面

原题是这样的：

一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来的正负数之间相对顺序。
比如： input: 1,7,-5,9,-12,15 ，ans: -5,-12,1,7,9,15 。且要求时间复杂度O(N),空间O(1) 。

    OK，下面咱们就来试着一步一步解这道题，如下5种思路（从复杂度O(N^2)到O(N*logN)，从不符合题目条件到一步步趋近于条件)）：

1. 最简单的，如果不考虑时间复杂度，最简单的思路是从头扫描这个数组，每碰到一个正数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该正数放入这个空位。由于碰到一个正，需要移动O(n)个数字，因此总的时间复杂度是O(n２)。
2. 既然题目要求的是把负数放在数组的前半部分，正数放在数组的后半部分，因此所有的负数应该位于正数的前面。也就是说我们在扫描这个数组的时候，如果发现有正数出现在负数的前面，我们可以交换他们的顺序，交换之后就符合要求了。
   因此我们可以维护两个指针，第一个指针初始化为数组的第一个数字，它只向后移动；第二个指针初始化为数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是正而第二个指针指向的数字是负数，我们就交换这两个数字。
   但遗憾的是上述方法改变了原来正负数之间的相对顺序。所以，咱们得另寻良策。

3. 首先，定义这样一个过程为“翻转”：(a1,a2,...,am,b1,b2,...,bn) --> (b1,b2,...,bn,a1,a2,...,am)。其次，对于待处理的未排序整数数组，从头到尾进行扫描，寻找(正正...正负...负负)串；每找到这样一个串，则计数器加1；若计数为奇数，则对当前串做一个“翻转”；反复扫描，直到再也找不到(正正...正负...负负)串。

   此思路来自朋友胡果果，空间复杂度虽为O(1)，但其时间复杂度O(N*logN)。更多具体细节参看原文：http://qing.weibo.com/1570303725/5d98eeed33000hcb.html。故，不符合题目要求，继续寻找。

4. 我们可以这样，设置一个起始点j, 一个翻转点k,一个终止点L，从右侧起，起始点在第一个出现的负数, 翻转点在起始点后第一个出现的正数,终止点在翻转点后出现的第一个负数(或结束)。

   如果无翻转点, 则不操作，如果有翻转点, 则待终止点出现后, 做翻转, 即ab => ba 这样的操作。翻转后, 负数串一定在左侧, 然后从负数串的右侧开始记录起始点, 继续往下找下一个翻转点。

   例子中的就是(下划线代表要交换顺序的两个数字)：

   1, 7, -5, 9, -12, 15  
   第一次翻转: 1, 7, -5, -12,9, 15   =>  1, -12, -5, 7, 9, 15
   第二次翻转: -5, -12, 1, 7, 9, 15

   此思路2果真解决了么?NO，用下面这个例子试一下，我们就能立马看出了漏洞：
   1, 7, -5, -6， 9, -12, 15（此种情况未能处理）
   1 7 -5 -6 -12 9 15
   1 -12 -5 -6 7 9 15
   -6 -12 -5 1 7 9 15   (此时，正负数之间的相对顺序已经改变，本应该是-5，-6，-12，而现在是-6 -12 -5)
5. 看来这个问题的确有点麻烦，不过我们最终貌似还是找到了另外一种解决办法，正如朋友超越神所说的：从后往前扫描，遇到负数，开始记录负数区间，然后遇到正数，记录前面的正数区间，然后把整个负数区间与前面的正数区间进行交换，交换区间但保序的算法类似（a,bc->bc,a）的字符串原地翻转算法。交换完之后要继续向前一直扫描下去，每次碰到负数区间在正数区间后面，就翻转区间。下面，将详细阐述此思路4。

思路5之区间翻转