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

C'est très simple
Utilisez le tri par comptage
Supposons que votre plage de nombres soit de 0 à 65535, définissez un tableau count[65536] (cet espace est une constante et n'a rien à voir avec n, il est donc O(1 )), les valeurs initiales sont toutes 0.
Supposons que nous ayons les nombres suivants :
100
200
300
119
0
6
...
Puis pour chacun de ces nombres, Enregistrez-les tous en nombre :
100 => count[100]
200 => count[200]
300 => count[300]
119 => count[119]
0 = > [0]
6 => count[6]
...
C'est-à-dire :
Tout d'abord, parcourez tous ces nombres pour obtenir le numéro de chaque nombre de 0 à 65535 (dans le tableau count)
Ensuite, parcourez le tableau de comptage dans ordre , count[n] = m, puis m n nombres sont affichés (par exemple, count[3] = 2, Cela signifie alors qu'il y a deux nombres 3), qui sont affichés en séquence, et finalement le résultat peut être obtenu.
Lors de la sortie :
Affichez d'abord les nombres impairs count[1], count[3]...
Et puis affichez les nombres pairs count[0],count[2]...
Analyse de complexité :
Le premier parcours est O(n), le deuxième parcours est O(1), qui est une constante, donc la complexité temporelle finale est O(n), et la complexité spatiale est O(1)

PS : Cet algorithme est très simple, je pense que tout le monde peut le faire, mais cette question est trop perverse et fera généralement peur à l'intervieweur

Answer 2

O=liste d'origine

N=[Aucun]*2n
pour je dans O :

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

Le principal problème est l'espace. Cela ne devrait pas être possible sans occuper un espace 2n. Parce que la situation est compliquée, il est impossible de déterminer qu'un espace constant suffit !

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

L'implémentation de js devrait être comme ceci. Lorsqu'il y a un nombre pair, un est libéré, puis ajouté à la fin et s'arrête lorsque le dernier du tableau initial est traité. Reportez-vous au code précédent de moling3650. .

Answer 4

J'ai juste aimé @白丁 et quelqu'un l'a immédiatement voté contre
Certaines personnes peuvent penser que la complexité de l'espace n'est pas constante après avoir postulé pour n-1 espaces.
J'ai utilisé php pour vérifier. En fait, l'augmentation de la mémoire est une constante. La quantité de mémoire augmentée testée par php5.4 est : 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

Existe-t-il un tri avec une complexité temporelle de O(n) ?

Answer 6

Après avoir lu les commentaires, je pensais au début que cette question n'avait pas de solution, mais en sortant du travail aujourd'hui, j'ai soudain eu une idée et j'ai pensé à une méthode. Après une brève vérification, j'ai découvert que c'était bien le cas. possible.
Cet algorithme ne nécessite que O(1) espace et O(n) temps, et ne modifiera pas l'ordre relatif entre les nombres impairs et les nombres pairs dans le tableau d'origine, ce qui répond pleinement aux exigences de la question. Aujourd'hui, je parlerai d'abord de l'idée de l'algorithme, et je prendrai le temps de terminer le programme demain.

Pour faire simple, il analyse chaque élément d'avant en arrière lors de l'analyse, deux pointeurs sont utilisés, l'un est utilisé pour le parcours régulier (c'est le i que nous utilisons habituellement pour parcourir le tableau); pointe vers le premier du tableau Les nombres pairs, appelés ici 偶数指针, sont initialisés à -1.

Le parcours commence. Pour chaque élément, il est réparti selon les situations suivantes :

1. L'élément est un nombre impair, et il y a un nombre pair devant lui (le pointeur pair est supérieur ou égal à 0), échangez ces deux nombres

2. L'élément est un nombre impair, et il n'y a pas de nombre pair devant lui (le pointeur pair est -1), aucune opération n'est effectuée et le prochain tour de parcours continue

3. L'élément est un nombre pair, et son élément précédent est un nombre pair (notez qu'il s'agit de l'élément précédent, pas de l'élément pointé par le pointeur pair), échangez ces deux nombres

4. L'élément est un nombre pair et son élément précédent est un nombre impair. À ce stade, le pointeur pair doit être -1 et l'attribuer à l'index de l'élément actuel (c'est-à-dire i). )

Ceci est répété jusqu'à l'avant-dernier élément, et le dernier élément nécessite un traitement spécial : s'il s'agit d'un nombre impair, suivez les étapes ci-dessus 1 s'il s'agit d'un nombre pair, aucun traitement n'est effectué et le parcours est effectué. complété. .

Par exemple, 1 2 3 4 5 6, voici l'état du tableau après chaque tour de parcours ([] représente l'élément actuellement parcouru et l'élément pointé par le pointeur pair) :

[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] // Terminé

Autre exemple, 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] // Terminé

Answer 7

Putain de merde, il est immédiatement devenu évident que JavaScript est le meilleur langage au monde

Les tableaux sont des listes chaînées et prennent en charge diverses opérations, putain

Supplément : Ne faites pas attention à moi, PHP est le meilleur langage du monde, j'avais tort

Remarque supplémentaire : ceux qui disent que je ne comprends pas les structures de données ne comprennent probablement pas mon ton taquin...