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

很簡單的
用計數排序
假定你的數字範圍在0到65535範圍之內，定義一個數組count[65536]（這個空間是常數，和n無關，所以是O(1) )，初值全部為0。
那麼假設有下面這些數字：
100
200
300
119
0
6
...
那麼對於每個這個數字，都做在count中記錄一下：
100 => count[100]
200 => count[200]++
300 => count[300]++
119 => count[119]++
0 => count[0]++
6 => count[6]++
...
也就是說：
首先，遍歷一遍所有這些數字就可得到0~65535每個數字的個數（在count數組中）
然後，再順序歷count數組，count[n] = m，則輸出m個n，（比如說有count[3] = 2, 那麼說明有2個數字3），依序輸出，最後可得結果。
在輸出時：
先輸出奇數count[1],count[3]...
再輸出偶數count[0],count[2]...
複雜度分析：
第一次遍歷是O( n)，第二次遍歷是O(1)，為常數，所以最後的時間複雜度為O(n)，而空間複雜度為O(1)

PS:這個演算法很簡單，相信大家都會，只是這個題太過於變態了，一般會把麵試者嚇住

Answer 2

O=orgin list

N=[None]*2n
for i in O:

odd=0
even=n
if int(i/2)==i/2:
    N[even]=i
    even+=1
else:
    N[odd]=i
    odd+=1

主要是空間問題，不佔用一個2n的空間應該是不能實現的，因為情況複雜，沒辦法確定常數空間就夠用！

Answer 3

var l = [1, 2, 4, 6, 3, 5]
var i=0, item, last = l[l.length-1], count=0;
while(i<l.length){
  count++;
  item = l[i];
  if(item == last){
    break;
  }
  if(item % 2 == 0){
    l.splice(i, 1);
    l.push(item);
  }else{
    i++;
  }
}
console.log(count); //循环执行了多少次
console.log(l); //最后结果

js實作應該是這樣的，偶數時釋放一個，然後追加到末尾,當處理到初始數組最後一個時停止。 參考了前面moling3650的程式碼。 。

Answer 4

剛我讚了@白汀 馬上有人踩
可能有人覺得申請了n-1個空間，空間複雜度不是常量。
我用php來輸出來驗證下，事實上增加的記憶體是常數，php5.4測試增加記憶體量為：160

<?php
$arr = range(1,20);  //生成1-20组成的数组
$n = count($arr); //统计数组个数
$old = memory_get_usage(); //统计页面占用内存

/* 开始处理数组 */
for($i=0;$i<$n;$i++){
    if($arr[$i]%2==0){
        $arr[] = $arr[$i];
        unset($arr[$i]);
    }
}
/* 处理结束 */

echo memory_get_usage()-$old; //输出当前占用内存减去原来内存，修改前面数组个数range(1,20)，range(1,20000)等，这里输出值固定为：160

var_dump($arr); //输出数组，数组下标到了3n-1,可能会觉得申请了n-1的空间

Answer 5

有時間複雜度為O(n)的排序嗎

Answer 6

看了評論，開始我也以為這個題目無解，但是今天下班路上突然靈機一動，想到一個方法，簡單驗證了一下，發現確實可以。
這個演算法只需要O(1)的空间，O(n)的時間，並且不會改變原數組中奇數和偶數之間的相對順序，完全符合題目要求。今天先說一下演算法思路，明天抽空把程式補上。

簡單來說就是從前到後掃描各個元素，掃描時使用2個指針，一個用來進行常規遍歷（就是平時我們遍歷數組使用的i）；另一个始终指向数组中的第一个偶数，这里称为偶数指针，初始化为-1。

遍歷開始，對於每一個元素，分為以下幾種情況：

1. 該元素為奇數，且它之前有偶數（偶數指針大於等於0），交換這兩個數

2. 該元素為奇數，且它之前沒有偶數（偶數指針為-1），不做任何操作，繼續下一輪遍歷

3. 該元素為偶數，並且它的前一個元素為偶數（注意是前一個元素，不是偶數指針指向的那個元素），交換這兩個數

4. 該元素為偶數，並且它的前一個元素為奇數，此時偶數指針一定是-1，将其赋值为当前元素的索引（即i，將其賦值為當前元素的索引（即i）

如此一直重複到倒數第二個元素，而對於最後一個元素需要特殊處理：如果它是奇數則按照上面1的步驟來處理；如果它是偶數，則不做任何處理，遍歷完成。

舉個例子，1 2 3 4 5 6，下面是每一輪遍歷之後數組的狀態（[]表示當前遍歷到的元素和偶數指針指向的元素）：

[1] 2 3 4 5 6
1 [2] 3 4 5 6
1 3 [2] 4 5 6
1 3 [4] [2] 5 6
1 3 5 [2] [4] 6
1 3 5 [2] 4 [6] // 完成

再舉個例子，1 2 4 6 8 5 7 3：

[1] 2 4 6 8 5 7 3
1 [2] 4 6 8 5 7 3
1 [4] [2] 6 8 5 7 3
1 [4] 6 [2] 8 5 7 3
1
1 [4] 6 [2] 8 5 7 3
1
1 [4] 6 [2] 8 5 7 3

1🎜1 [4] 6 [2] 8 5 7 3🎜1 [4] 6 8 [2] 5 7 3🎜1 5 [6] 8 2 [4] 7 3🎜1 5 7 [8] 2 4 [6] 3🎜1 5 7 3 [2] 4 6 [8] // 完成🎜

Answer 7

臥槽，瞬間體現 JavaScript 是世界上最好的語言了

數組即鍊錶，支援各種操作，屌吧

補：別睬我了，PHP 是世界上最好的語言，我錯了

再補：說我不懂資料結構的大概都沒 get 到我調侃的語氣吧...