python - 给定一个2n长的数组将奇数放在偶数前面

Question

给定一个2n长数组，其中n个奇数和n个偶数，对数组进行排序将奇数放在前半部分，偶数放在后半部分。要求：

1. 不改变原来的奇偶各自的相对顺序

2. 只申请常数的空间

3. 时间复杂度为O(n)

举例：给出1 2 3 4 5 6
排序后为 1 3 5 2 4 6

PS：请一定仔细阅读3个条件，去掉其中任意一个都变得简单，并且网上我搜到的答案都是缺少其中某个条件的。因此我怀疑这题是否有解。

---

看了大家的回答，基本可以分为2种情况：

1. 用链表可以轻易解决这道题，当然如果把数组转成链表因为需要申请2n长度的next数组，所以认为还是申请额外空间了

2. 只管输出，如果只要求输出结果那遍历2遍就行了，但这样题目变得太过简单

因为这是一道面试题，我想可以从上面2方面和面试官沟通，我只是凭记忆写下这题，其中也许有自己的一些思维定势（比如没有强调一定是数组，或者没有强调必须要求数组排序只要求输出）。看了大家的讨论还是很有启发的。

---

找到了国外的链接，看了一圈讨论大部分认为没有O(n)时间O(1)空间的解法
https://www.careercup.com/question?id=5201559730257920

---

另外说下我自己对这题的一个思考，可以观察到，假如一个数组是符合最终条件的，那么发现当且仅当只交换相邻的两个奇偶数是不会破坏相对顺序的，那么只需给出一个策略找出从最终状态转到题目起始状态的就行了。
另外，不要纠结于奇偶分别的大小问题，比如4 5 3 1 2 6和2 1 3 5 4 6是等价的，只是一个简单的替换，只要将奇数按1 3 5……这样的顺序，偶数按2 4 6……这样的顺序排好就行了。

Answer 1

在你的3個條件限制下，陣列不行，鍊錶可以。

Answer 2

用鍊錶還是很容易的吧，只是改變指針就可以了，遍歷一次搞定，遇到偶數插入隊尾（只改指針不申請內存），奇數就不管它，但如果還要對奇偶數各自排序基本不會有O(n)的演算法

L = [1, 2, 3, 4, 5, 6]
index = 0
for _ in range(len(L)):
    if L[index] % 2 == 1:
        index += 1
    else:
        L.append(L.pop(index))
print(L)

#include <iostream>
#include <list> 

using namespace std;

int main() {
    list<int> L;
    int n = 3; 
    // 初始化链表
    for(int i = 1; i <= n * 2; i++)
        L.push_back(i);
    // 划分奇偶数
    for(list<int>::iterator it = L.begin(); 0 < n; ++it){
        if(*it % 2 == 0){  // 如果是偶数
            L.push_back(*it); // 插入尾节点 O(1)
            L.erase(it); // 删除节点 O(1)
            n -= 1;
        }      
    }
    // 打印链表
    for(list<int>::iterator it = L.begin(); it != L.end(); ++it)
        cout << *it << ' ';
    cout << endl;
        
    return 0;
}

已經很多人說了， 用鍊錶是很容易實現的，但是用數組卻不行（保持穩定性，時間O(n)，空間O(1)），如果誰可以，show your code，讓我們膜拜你。

初看無解的問題，貌似也有解決的辦法的，待我整理一下。

def Foo(L):
    # L = [0, 2, 4, 1, 3, 5]
    length = len(L)
    sk = max(*L, length) + 1# secret key
    # 32位的话最多是支持4万多的数据量，且最大值也不超过46340
    assert sk < 46340, 'sk must be less than 46340' 
    li = 0                  # left index
    ri = length - 1         # right index
    uli = li                # unsorted left index
    uri = ri                # unsorted right index
    lli = length // 2 - 1   # left last index
    rfi = lli + 1           # right first index
    # 第一个循环先区别就位和未能就位的元素，同时将index信息加密到未能就位的元素数据中
    # 这里用的加密文法是number = -(num + sk * indnx),将其变成一个负值
    # 解密可以用index, num = pmod(abs(number), sk)来解密
    while li <= ri:
        # 左边扫描到奇数
        if L[li] % 2 == 1:
            L[li], L[uli] = L[uli], L[li]
            li += 1
            uli += 1
        # 右边扫描到偶数
        elif L[ri] % 2 == 0:
            L[ri], L[uri] = L[uri], L[ri]
            ri -= 1
            uri -= 1
        # 当左为偶，且右为奇
        else:
            L[li], L[ri] = L[ri], L[li]
            L[li] = -(L[li] + sk * lli) # 加密乱序的元素
            lli -= 1
            L[ri] = -(L[ri] + sk * rfi) # 加密乱序的元素
            rfi += 1
            li += 1
            ri -= 1
    print(L) # 加密后 [-39, -20, -1, -89, -70, -51]
    # 解密
    for i in range(uli, uri):
        if L[i] < 0:
            index, number = pmod(abs(L[i]), sk)
            next_num = L[index]
            while next_num < 0:                
                L[index] = number
                index, number = pmod(abs(next_num), sk)
                next_num = L[index]
    print(L) # 解密 [1, 3, 5, 0, 2, 4]
    return L

最好不要用大於length數字來測試，如果數據不大的話，應該沒問題的，否則就要考慮溢出的問題了。

Answer 3

我是這樣想拉，不知道你覺得怎麼樣:

就從陣列的頭開始走，碰到奇數不動，碰到偶數就把它放到數組的最後，直到搬動了 n 個偶數為止。

1. 奇數偶數各自順序不變
2. 只需要一個整數記目前搬動幾個了
3. 就最差 2n 步(偶數都在後面的情況)

---

P.S. 為什麼給負分呢? 如果覺得答案有任何不妥的地方，可以先評論、討論之後再給別人負分，我不覺得有必要踩在這裡認真討論的人，對於負分充滿著疑惑. ..

Answer 4

我覺得是不可能的，其實歸根究底，這是一個排序問題。
我們假設使用快排(當然不滿足穩定性問題，這裡只是隨便說，想要穩定性可以用二叉樹來排序)，那麼只要把比較條件設為奇數比偶數大就可以了。
但是很明顯排序問題只有在某些特殊情況下才能O(n)。
所以我覺得不可能。

Answer 5

作為一般的排序問題來看，會讓人覺得不可能，但是這個題目雖然3個條件很苛刻。
也有一些有利條件可以利用，重要的2點是：

1. 奇數和偶數一樣多，所有陣列長度就是 n + n

2. 奇數和偶數保持原有順序，不需要按大小進行排序

我用golang實作如下：

package main

import "fmt"

func main() {
    var n = 4
    // var intArr = []int{12, 2, 4, 6, 5, 1, 7, 3}
    // var intArr = []int{1, 2, 3, 4, 5, 6, 7, 8}
    var intArr = []int{1, 2, 4, 6, 8, 3, 5, 7}
    var odd = 0
    var even = 2*n - 1

    for i := 0; i < len(intArr); i++ {
        if i > even {
            break
        }

        // fmt.Printf("before: %v\n", intArr)
        if intArr[i]%2 == 0 { // even number
            intArr[even], intArr[i] = intArr[i], intArr[even]
            even--
        } else { // odd number
            intArr[odd], intArr[i] = intArr[i], intArr[odd]
            odd++
        }
        // fmt.Printf("after : %v\n", intArr)
    }

    // print result
    for i := 0; i < odd; i++ {
        fmt.Println(intArr[i])
    }
    for i := even; i > odd-1; i-- {
        if intArr[i]%2 != 0 {
            fmt.Println(intArr[i])
        }
    }
    for i := 2*n - 1; i > even; i-- {
        fmt.Println(intArr[i])
    }
    for i := odd; i < even+1; i++ {
        if intArr[i]%2 == 0 {
            fmt.Println(intArr[i])
        }
    }
}

Answer 6

原題的要求翻譯下
1） 時間複雜度為線性
2） 空間複雜度O(k)
3) 穩定的
時間複雜度為O(n)的話，意味著已經不能是比較排序了，比較排序的平均時間複雜度最好是好O(nlgn)，例如快速排序等。
這個已經是《演算法導論》的被數學證明的結論了。
時間為線性的只有計數、桶和基數，見https://www.byvoid.com/blog/sort-radix
也就是排序只有
1） 計數- 時間複雜度O(n) 空間複雜度O( k+n)

http://www.geeksforgeeks.org/counting-sort/

2) 桶排序 - O(n) 空間複雜度 O(k+n)
http://www.growingwiththeweb.com/2015/06/bucket-sort.html

3） 基數排序 O(n) 和 O(n+k)

所以個人覺得這題無解。
BTW： 建議樓主好好看看下面這個連結
http://bigocheatsheet.com/

本人學校畢業已久，這些結論性的東西記得不是很清楚了，也就是本人不對上述結論性的東西負責 :-)
樓主可以基於上面文章再佐證下。

但基於比較的時間複雜度平均不超過O(nlogn) 這個本人是肯定的，所以建議從基數、桶排序、基數這3者裡找找，看看哪個更接近你的要求。

Answer 7

這裡有一個類似問題的答案：

https://www.quora.com/Given-an-array-of-integers-how-do-I-re-arrange-the-numbers-such-that-odd-numbers-occupy-odd-position-and -even-numbers-occupy-even-position

你這個題解法跟它是相同的，因為要求裡只有一處不同：奇數在奇數索引位置，偶數在偶數索引位置。連結裡的第一個答案是最接近你想要的答案，為什麼說只是接近，是因為它要求原始數組能容納少量額外數據。

其實我還懷疑，面試官問你的問題，會不會還有隱含條件沒跟你講清楚，比如2n數組本身是個有序數組，情況就大不一樣了。

Answer 8

看了一下題目，簡單的想了一下，思路如下：

如果是給出的數組，就沒有辦法保持相對順序不變。 下面程式碼只能滿足條件2和3：

for (i=0, j= 2n-1; i<n, j>n; ){
    if((n[i] % 2 == 1) && (n[j] % 2==0)){
        i++;
        j--;
    }
    
    if((n[i] % 2 == 0) && (n[j] % 2)==1){
           swap(n[i],n[j]);
           i++;
           j--;
    }
    
    if((n[i] %2 == 0) && (n[j] %2 == 0)){
        j--;
    }
    
    if((n[i] %2 == 1) && (n[j] %2 == 1)){
        i++;
    }
}

就是分別從最開始和最後面進行檢查，四種情況，分別判斷一下。

如果給的是鍊錶，上述的3個條件很容易滿足。

另：莫名其妙的被踩。 。 。

Answer 9

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.06.md

見其中舉一反三中的說明。

論文連結如下

《 STABLE MINIMUM SPACE PARTITIONING IN LINEAR TIME 》

Answer 10

感覺是無解的。

即便是這篇文章也做了一個假設，比較兩個數的f-value是常數時間，可以理解為每個數字自帶位置資訊。
http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf

下面是對無解我自己的分析：

這個數列是一個置換群，我們知道從一個長度為n的序列通過數字的兩兩置換變成另一個序列，最多需要n-1次置換操作，前提是我們知道每個數字所需要置換到的位置。但由於沒有辦法知道每個數字要置換到的位置（知道也沒地方儲存），也沒有顯而易見的能夠對每個數字在常數時間內求得其置換位置的方法（其實我更傾向於不存在這樣的方法）。所以這應該是不可能的。

有額外空間可以用輔助數組。
有額外時間可以用類似歸併排序的方法，非遞歸實現，因為是只分奇偶，可以原地交換。