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]++
...
つまり:
まず、これらの数値をすべて走査します。 (count 配列内の) 0 ～ 65535 の各数値を取得するには
次に、 で count 配列をシーケンス で走査し、 count[n] = m を出力し、 m n を出力します (例: count[3] = 2 の場合、数値が 2 つあることを意味します 3)、それらを順番に出力し、最終的に結果を取得します。
出力時:
最初に奇数を出力 count[1], count[3]...
次に偶数を出力 count[0],count[2]...
複雑さの分析:
最初のトラバーサルは O(n)、2 番目のトラバーサルは O(1) で、これは定数であるため、最終的な時間計算量は O(n)、空間計算量は O(1) です

追伸: このアルゴリズムは非常に単純で、誰でもできると思いますが、この質問はあまりにも変態的で、通常は面接官を怖がらせるでしょう

Answer 2

O=元のリスト

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

リーリー

主な問題はスペースです。状況は複雑なので、一定のスペースがあれば十分であると判断することはできません。

Answer 3

リーリー

js の実装は次のようになります。偶数がある場合は 1 つ解放され、最後に追加され、最初の配列の最後の 1 つが処理された時点で停止します。 moling3650 の以前のコードを参照してください。 。

Answer 4

私は @白丁 が好きだったのですが、すぐに誰かが反対票を投じました
n-1 個のスペースを申請した後、スペースの複雑さが一定ではないと考える人もいるかもしれません。
実際にphp5.4でテストしたメモリ増加量は160です。 リーリー

Answer 5

時間計算量が O(n) のソートはありますか?

Answer 6

コメントを読んだ後、最初はこの質問には解決策がないと思いましたが、今日仕事を終える途中に突然アイデアが思いつき、簡単な検証の後、その通りであることがわかりました。可能。
このアルゴリズムは O(1) 空間と O(n) 時間のみを必要とし、元の配列内の奇数と偶数の間の相対順序を変更せず、質問の要件を完全に満たします。今日は最初にアルゴリズムのアイデアについて話します。明日は時間をかけてプログラムを完成させます。

簡単に言うと、スキャンの際に 2 つのポインターが使用されます。1 つは通常の走査に使用され、もう 1 つは常に配列を走査するために使用されます。配列の最初の数値を指します。ここでは i と呼ばれる偶数は 偶数指针 に初期化されます。 -1

要素ごとにトラバースが開始され、次の状況に分かれます。

1. 要素が奇数で、その前に偶数がある (偶数ポインタが

   以上)、これら 2 つの数値を交換します 0

2. 要素は奇数であり、その前に偶数がない (偶数ポインターは

   )、操作は実行されず、次のラウンドの走査が続行されます -1

3. 要素は偶数であり、その前の要素も偶数です (偶数ポインタが指す要素ではなく、前の要素であることに注意してください)。これら 2 つの数字を交換します

4. この要素は偶数であり、その前の要素は奇数です。このとき、偶数ポインターは

   である必要があり、それを現在の要素のインデックス (つまり -1) に割り当てます。 )i

これは最後から 2 番目の要素まで繰り返され、最後の要素には特別な処理が必要です。それが奇数の場合は、上記の手順に従います。

が偶数の場合は、処理は行われず、走査は行われます。完成しました。 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 [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 は世界で最高の言語です。私は間違っていました。

追記: 私がデータ構造を理解していないと言う人には、おそらく私のからかうような口調が理解できないでしょう...