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) アルゴリズムはありません。 リーリー リーリー

リンク リストを使用すると実装は簡単ですが、配列では実装できない (安定性、時間 O(n)、空間 O(1) を維持できる) と多くの人が言っています。もしできる人がいたら、コードを見せてください。 。

一見、解決できないように見える問題を整理してみましょう。

リーリー

のテストには長さより大きい数値を使用しないことが最善です。データが大きくない場合は問題ありません。そうでない場合は、オーバーフローの問題を考慮する必要があります。

Answer 3

私はこうしたいのですが、皆さんがどう思うか分かりません:

配列の先頭から開始し、奇数に遭遇した場合は移動しないでください。偶数に遭遇した場合は、n 個の偶数が移動されるまで、それを配列の最後に置きます。

リーリー

---

追伸：なぜ否定的な点を与えるのですか? 答えに何か間違っていると思うなら、他の人に否定的な点を与える前に、まずコメントして議論してください。ここで真剣に議論している人を踏みにじる必要はないと思います。疑問点だらけです…

Answer 4

結局のところ、これは並べ替えの問題だと思います。
クイックソートが使用されていることを前提としています (もちろん、安定性の問題を満たしていません。安定性が必要な場合は、バイナリツリーを使用してソートできます、とここで何気なく言っているだけです)。次に、比較条件を次のように設定します。奇数は偶数より大きい。
しかし、いくつかの特殊なケースでは、並べ替え問題が O(n) にしかならないことは明らかです。
だからそれは無理だと思います。

Answer 5

一般的な並べ替え問題として見ると不可能に思えるかもしれませんが、この問題には非常に厳しい条件が 3 つあります。
有利な条件もいくつかあります。重要な点は次の 2 つです。

1. 奇数は偶数と同数あり、すべての配列の長さは n + n です

2. 奇数と偶数は元の順序を維持し、サイズで並べ替える必要はありません

私は golang を使用して次の実装を行います:

リーリー

Answer 6

元の質問の要件を以下に翻訳します
1) 時間計算量は線形です
2) 空間計算量は O(k)
3) 安定した
時間計算量は O( n) は、比較ソートが不可能になったことを意味します。クイック ソートなどの比較ソートの最適な平均時間計算量は O(nlgn) です。
これはすでに数学的に証明された「アルゴリズム入門」の結論です。
線形時間を持つのは count、bucket、および radix だけです。 https://www.byvoid.com/blog/sort-radix を参照してください
つまり、並べ替えは
1) カウント - 時間計算量のみですO(n ) 空間計算量 O(k+n)

リーリー

2) バケットソート - O(n) 空間複雑度 O(k+n)
http://www.growingwiththeweb.com/2015/06/bucket-sort.html

3) 基数ソート O(n) および O(n+k)

したがって、私は個人的に、この質問には解決策がないと考えています。
ところで: 以下のリンクをよくご覧になることをお勧めします
http://bigochheatsheet.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 -そして偶数は偶数の位置を占めます

要件の違いが 1 つだけあるため、問題の解決策は同じです。奇数は奇数のインデックス位置にあり、偶数は偶数のインデックス位置にあります。リンク内の最初の答えが、希望するものに最も近い答えです。これが近い理由は、元の配列が少量の追加データを収容できる必要があるからです。

実際のところ、質問するときに面接官が明確に説明していない暗黙の条件があるのではないかと今でも疑っています。たとえば、2n 配列自体が順序配列である場合、状況は大きく異なります。

Answer 8

質問を読んで簡単に考えてみると、次のような考えになります:

それが指定された配列である場合、相対的な順序を変更しないで維持する方法はありません。 次のコードは条件 2 と 3 のみを満たすことができます:

リーリー

最初と最後から確認して、4つの状況をそれぞれ判断するだけです。

リンクリストが与えられれば、上記の 3 つの条件は簡単に満たされます。

別の人: 理由もなく踏まれました。 。 。

Answer 9

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

一例から推測する方法については、説明を参照してください。

論文リンクは以下の通りです

《線形時間での安定した最小空間分割》

Answer 10

解決策がないように感じます。

この記事でも、2 つの数値の f 値の比較は定数時間であると仮定していますが、それぞれの数値が独自の位置情報を持っていることがわかります。
http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf

以下は、No Solution についての私自身の分析です:

このシーケンスは、長さ n のシーケンスから、数値のペアごとの置換を通じて、最大 n-1 個の置換操作が必要であることがわかっています。前提として、各数値に必要な置換がわかっていることです。 . 場所へ。ただし、各数値が置換される位置を知る方法がない（保存する場所がない）ため、一定時間内に各数値の置換位置を見つける明白な方法はありません（実際には、それを好む）そのようなものはありません）メソッド）。したがって、これは不可能であるはずです。

余分なスペースがある場合は、補助配列を使用できます。
時間に余裕がある場合は、マージソートに似た非再帰的な実装を使用できます。奇数と偶数を分割するだけなので、その場で交換できます。