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

Ia sangat mudah
Gunakan pengisihan mengira
Andaikan julat nombor anda adalah dari 0 hingga 65535, tentukan kiraan tatasusunan[65536] (ruang ini adalah pemalar dan tiada kaitan dengan n, jadi ia adalah O(1)), nilai awal semuanya 0.
Andaikan kita mempunyai nombor berikut:
100
200
300
119
0
6
...
Kemudian untuk setiap nombor ini, Catat kesemuanya dalam kiraan:
100 => count[100]
200 => count[200]
300 => count[300]
119 => count[119]
0 = > [0]
6 => kira[6]
...
Maksudnya:
Mula-mula, ulangi semua nombor ini untuk mendapatkan nombor setiap nombor daripada 0 hingga 65535 (dalam tatasusunan kiraan)
Kemudian, lalui tatasusunan kiraan dalam susunan , kira[n] = m, kemudian m n nombor dikeluarkan, (contohnya, kiraan[3] = 2, Maka bermakna terdapat dua nombor 3), iaitu keluaran mengikut turutan, dan akhirnya hasilnya dapat diperolehi.
Apabila mengeluarkan:
Output pertama kiraan nombor ganjil[1], kira[3]...
Dan kemudian keluarkan kiraan nombor genap[0],kira[2]...
Analisis kerumitan :
Traversal pertama ialah O(n), traversal kedua ialah O(1), iaitu pemalar, jadi kerumitan masa akhir ialah O(n), dan kerumitan ruang ialah O(1)

PS: Algoritma ini sangat mudah, saya percaya semua orang boleh melakukannya, tetapi soalan ini terlalu menyeleweng dan biasanya akan menakutkan penemuduga

Answer 2

O=senarai asal

N=[Tiada]*2n
untuk i dalam O:

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

Masalah utama adalah ruang Ia tidak boleh dilakukan tanpa menduduki ruang 2n Kerana keadaannya rumit, adalah mustahil untuk menentukan bahawa ruang malar sudah mencukupi.

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); //最后结果

Pelaksanaan js sepatutnya seperti ini Apabila terdapat nombor genap, satu dilepaskan, kemudian ditambahkan pada penghujung, dan berhenti apabila tatasusunan awal yang terakhir diproses. Rujuk kod sebelumnya moling3650. .

Answer 4

Saya hanya menyukai @白丁 dan seseorang segera menolaknya
Sesetengah orang mungkin berpendapat bahawa kerumitan ruang tidak tetap selepas memohon ruang n-1.
Saya menggunakan php untuk mengeluarkan untuk mengesahkan Sebenarnya, peningkatan memori adalah malar Jumlah memori meningkat yang diuji oleh php5.4 ialah: 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

Adakah terdapat sebarang pengisihan dengan kerumitan masa O(n)?

Answer 6

Setelah membaca komen, saya rasa soalan ini pada mulanya tidak ada penyelesaian, tetapi dalam perjalanan saya untuk keluar kerja hari ini, saya tiba-tiba mendapat idea dan memikirkan satu kaedah Selepas pengesahan ringkas, saya dapati memang betul mungkin.
Algoritma ini hanya memerlukan O(1) ruang dan O(n) masa, dan tidak akan mengubah susunan relatif antara nombor ganjil dan nombor genap dalam tatasusunan asal, yang memenuhi sepenuhnya keperluan soalan. Hari ini saya akan bercakap tentang idea algoritma dahulu, dan saya akan meluangkan masa untuk menyiapkan program esok.

Secara ringkasnya, ia mengimbas setiap elemen dari hadapan ke belakang Apabila mengimbas, dua penunjuk digunakan, satu digunakan untuk traversal biasa (iaitu i yang biasa kami gunakan untuk melintasi tatasusunan); menunjuk kepada yang pertama dalam tatasusunan Nombor genap, di sini dipanggil 偶数指针, dimulakan kepada -1.

Traversal bermula Untuk setiap elemen, ia dibahagikan kepada situasi berikut:

1. Elemen ialah nombor ganjil, dan terdapat nombor genap di hadapannya (penunjuk genap lebih besar daripada atau sama dengan 0), tukar dua nombor ini

2. Elemen ialah nombor ganjil, dan tiada nombor genap sebelumnya (penunjuk genap ialah -1), tiada operasi dilakukan dan pusingan traversal seterusnya diteruskan

3. Elemen ialah nombor genap, dan elemen sebelumnya ialah nombor genap (perhatikan bahawa ia adalah elemen sebelumnya, bukan elemen yang ditunjuk oleh penunjuk genap), tukar dua nombor ini

4. Elemen ialah nombor genap, dan elemen sebelumnya ialah nombor ganjil Pada masa ini, penunjuk genap mestilah -1 dan menetapkannya kepada indeks elemen semasa (iaitu i. )

Ini diulang sehingga elemen kedua terakhir, dan elemen terakhir memerlukan pemprosesan khas: jika ia adalah nombor ganjil, ikut langkah di atas 1; jika ia adalah nombor genap, tiada pemprosesan dilakukan dan traversal adalah selesai.

Sebagai contoh, 1 2 3 4 5 6, berikut ialah keadaan tatasusunan selepas setiap pusingan traversal ([] mewakili elemen yang sedang dilalui dan elemen yang ditunjuk oleh penuding genap):

[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] // Lengkapkan

Contoh lain, 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] // Lengkap

Answer 7

Sial, jelaslah dengan serta-merta bahawa JavaScript ialah bahasa terbaik di dunia

Array ialah senarai terpaut dan menyokong pelbagai operasi, sial

Tambahan: Jangan perhatikan saya, PHP adalah bahasa terbaik di dunia, saya silap

Nota tambahan: Mereka yang mengatakan saya tidak faham struktur data mungkin tidak memahami nada usikan saya...