|
|
Posted on 2013-05-28 17:50 鑫龍 閱讀(564) 評論(0) 編輯 收藏 引用 所屬分類: JULY_程序員編程藝術
第二十七章：不改變正負數之間相對順序重新排列數組.時間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)，從不符合題目條件到一步步趨近于條件)）： - 最簡單的，如果不考慮時間復雜度，最簡單的思路是從頭掃描這個數組，每碰到一個正數時，拿出這個數字，并把位于這個數字后面的所有數字往前挪動一位。挪完之后在數組的末尾有一個空位，這時把該正數放入這個空位。由于碰到一個正，需要移動O(n)個數字，因此總的時間復雜度是O(n２)。
- 既然題目要求的是把負數放在數組的前半部分，正數放在數組的后半部分，因此所有的負數應該位于正數的前面。也就是說我們在掃描這個數組的時候，如果發現有正數出現在負數的前面，我們可以交換他們的順序，交換之后就符合要求了。
因此我們可以維護兩個指針，第一個指針初始化為數組的第一個數字，它只向后移動；第二個指針初始化為數組的最后一個數字，它只向前移動。在兩個指針相遇之前，第一個指針總是位于第二個指針的前面。如果第一個指針指向的數字是正而第二個指針指向的數字是負數，我們就交換這兩個數字。
但遺憾的是上述方法改變了原來正負數之間的相對順序。所以，咱們得另尋良策。 首先，定義這樣一個過程為“翻轉”：(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。故，不符合題目要求，繼續尋找。 我們可以這樣，設置一個起始點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)- 看來這個問題的確有點麻煩，不過我們最終貌似還是找到了另外一種解決辦法，正如朋友超越神所說的：從后往前掃描，遇到負數，開始記錄負數區間，然后遇到正數，記錄前面的正數區間，然后把整個負數區間與前面的正數區間進行交換，交換區間但保序的算法類似（a,bc->bc,a）的字符串原地翻轉算法。交換完之后要繼續向前一直掃描下去，每次碰到負數區間在正數區間后面，就翻轉區間。下面，將詳細闡述此思路4。
思路5之區間翻轉 其實上述思路5非常簡單，既然單個翻轉無法解決問題，那么咱們可以區間翻轉阿。什么叫區間翻轉?不知讀者朋友們是否還記得本blog之前曾經整理過這樣一道題，微軟面試100題系列第10題，如下： 10、翻轉句子中單詞的順序。
題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。例如輸入“I am a student.”，則輸出“student. a am I”。而此題可以在O(N)的時間復雜度內解決： 由于本題需要翻轉句子，我們先顛倒句子中的所有字符。這時，不但翻轉了句子中單詞的順序，而且單詞內字符也被翻轉了。我們再顛倒每個單詞內的字符。由于單詞內的字符被翻轉兩次，因此順序仍然和輸入時的順序保持一致。
以上面的輸入為例：翻轉“I am a student.”中所有字符得到“.tneduts a ma I”，再翻轉每個單詞中字符的順序得到“students. a am I”，正是符合要求的輸出(編碼實現，可以參看此文：http://zhedahht.blog.163.com/blog/static/254111742007289205219/)。
對的，上述思路3就是這個意思，單詞翻轉便相當于于區間翻轉，既如此，咱們來驗證下上述思路2中那個測試用例，如下： 1, 7, -5, -6， 9, -12, 15
1 7 -5 -6 -12 9 15
-12 -6 -5 7 1 9 15 (借用單詞翻轉的方法，先逐個數字翻轉，后正負數整體原地翻轉)
-5 -6 -12 1 7 9 15
思路5再次被質疑 但是，我還想再問，問題至此被解決了么?真的被KO了么?NO，咱們來看這樣一種情況，正如威士忌所說： 看看這個數據，+-+-+-+-+------+，假如Nminus 等于 n/2，由于前面都是+-+-+-，區間交換需要 n/2/2 = n/4次，每次交換是 T(2*(Nminus + Nplus)) >= T(n)，n/4 * T(n) = T(n*n/4)=O(n^2)。 還有一種更壞的情況，就是+-+-+-+-+------+這種數據可能，后面一大堆的負數，前面正負交替。所以，咱們的美夢再次破滅，路漫漫其修遠兮，此題仍然未找到一個完全解決了的方案。
|