Sous vos trois conditions, les tableaux ne sont pas possibles, mais les listes chaînées le sont.

Il est très simple d'utiliser une liste chaînée. Il suffit de changer le pointeur. Il est parcouru une fois. Si vous rencontrez un nombre pair, insérez-le à la fin de la file d'attente (changez uniquement le pointeur et ne demandez pas de mémoire). . Ignorez le nombre impair. Mais si vous devez toujours séparer les nombres impairs et pairs, il n'y a fondamentalement pas d'algorithme O(n) pour le tri

L = [1, 2, 3, 4, 5, 6]
index = 0
for _ in range(len(L)):
    if L[index] % 2 == 1:
        index += 1
    else:
        L.append(L.pop(index))
print(L)

#include <iostream>
#include <list> 

using namespace std;

int main() {
    list<int> L;
    int n = 3; 
    // 初始化链表
    for(int i = 1; i <= n * 2; i++)
        L.push_back(i);
    // 划分奇偶数
    for(list<int>::iterator it = L.begin(); 0 < n; ++it){
        if(*it % 2 == 0){  // 如果是偶数
            L.push_back(*it); // 插入尾节点 O(1)
            L.erase(it); // 删除节点 O(1)
            n -= 1;
        }      
    }
    // 打印链表
    for(list<int>::iterator it = L.begin(); it != L.end(); ++it)
        cout << *it << ' ';
    cout << endl;
        
    return 0;
}

Beaucoup de gens ont dit qu'il était facile à implémenter en utilisant des listes chaînées, mais pas avec des tableaux (maintien de la stabilité, temps O(n), espace O(1)). Si quelqu'un le peut, montrez votre code et laissez-nous vous adorer. .

À première vue, il semble y avoir une solution au problème qui semble insoluble.

def Foo(L):
    # L = [0, 2, 4, 1, 3, 5]
    length = len(L)
    sk = max(*L, length) + 1# secret key
    # 32位的话最多是支持4万多的数据量，且最大值也不超过46340
    assert sk < 46340, 'sk must be less than 46340' 
    li = 0                  # left index
    ri = length - 1         # right index
    uli = li                # unsorted left index
    uri = ri                # unsorted right index
    lli = length // 2 - 1   # left last index
    rfi = lli + 1           # right first index
    # 第一个循环先区别就位和未能就位的元素，同时将index信息加密到未能就位的元素数据中
    # 这里用的加密文法是number = -(num + sk * indnx),将其变成一个负值
    # 解密可以用index, num = pmod(abs(number), sk)来解密
    while li <= ri:
        # 左边扫描到奇数
        if L[li] % 2 == 1:
            L[li], L[uli] = L[uli], L[li]
            li += 1
            uli += 1
        # 右边扫描到偶数
        elif L[ri] % 2 == 0:
            L[ri], L[uri] = L[uri], L[ri]
            ri -= 1
            uri -= 1
        # 当左为偶，且右为奇
        else:
            L[li], L[ri] = L[ri], L[li]
            L[li] = -(L[li] + sk * lli) # 加密乱序的元素
            lli -= 1
            L[ri] = -(L[ri] + sk * rfi) # 加密乱序的元素
            rfi += 1
            li += 1
            ri -= 1
    print(L) # 加密后 [-39, -20, -1, -89, -70, -51]
    # 解密
    for i in range(uli, uri):
        if L[i] < 0:
            index, number = pmod(abs(L[i]), sk)
            next_num = L[index]
            while next_num < 0:                
                L[index] = number
                index, number = pmod(abs(next_num), sk)
                next_num = L[index]
    print(L) # 解密 [1, 3, 5, 0, 2, 4]
    return L

Il est préférable de ne pas utiliser de nombres plus grands que la longueur pour tester Si les données ne sont pas volumineuses, cela devrait aller, sinon vous devrez considérer des problèmes de débordement.

J'ai tellement envie de réussir, je ne sais pas ce que vous en pensez :

Commencez simplement par la tête du tableau et ne bougez pas lorsque vous rencontrez un nombre impair, placez-le à la fin du tableau, jusqu'à ce que n nombres pairs aient été déplacés.

1. 奇數偶數各自順序不變
2. 只需要一個整數記目前搬動幾個了
3. 就最差 2n 步(偶數都在後面的情況)

P.S. Pourquoi donner des notes négatives ? ​​Si vous pensez qu'il y a quelque chose qui ne va pas dans la réponse, vous pouvez d'abord commenter et en discuter avant de donner des notes négatives aux autres. Je ne pense pas qu'il soit nécessaire de marcher sur ceux qui discutent sérieusement ici. . Je suis plein de notes négatives...

Je pense que c'est impossible. En dernière analyse, c'est un problème de tri.
Nous supposons que le tri rapide est utilisé (bien sûr, cela ne répond pas au problème de stabilité, je dis juste avec désinvolture, si vous voulez de la stabilité, vous pouvez utiliser un arbre binaire pour trier), puis définissez simplement la condition de comparaison sur impaire les nombres sont plus grands que les nombres pairs.
Mais il est évident que le problème de tri ne peut être O(n) que dans certains cas particuliers.
Donc je pense que c’est impossible.

Considéré comme un problème général de tri, cela peut sembler impossible, mais cette question comporte trois conditions très exigeantes.
Il existe également quelques conditions favorables dont on peut profiter. Les deux points importants sont :

1. Il y a autant de nombres impairs que de nombres pairs, et la longueur de tous les tableaux est n n

2. Les nombres impairs et pairs conservent leur ordre d'origine et n'ont pas besoin d'être triés par taille

J'utilise Golang pour implémenter ce qui suit :

package main

import "fmt"

func main() {
    var n = 4
    // var intArr = []int{12, 2, 4, 6, 5, 1, 7, 3}
    // var intArr = []int{1, 2, 3, 4, 5, 6, 7, 8}
    var intArr = []int{1, 2, 4, 6, 8, 3, 5, 7}
    var odd = 0
    var even = 2*n - 1

    for i := 0; i < len(intArr); i++ {
        if i > even {
            break
        }

        // fmt.Printf("before: %v\n", intArr)
        if intArr[i]%2 == 0 { // even number
            intArr[even], intArr[i] = intArr[i], intArr[even]
            even--
        } else { // odd number
            intArr[odd], intArr[i] = intArr[i], intArr[odd]
            odd++
        }
        // fmt.Printf("after : %v\n", intArr)
    }

    // print result
    for i := 0; i < odd; i++ {
        fmt.Println(intArr[i])
    }
    for i := even; i > odd-1; i-- {
        if intArr[i]%2 != 0 {
            fmt.Println(intArr[i])
        }
    }
    for i := 2*n - 1; i > even; i-- {
        fmt.Println(intArr[i])
    }
    for i := odd; i < even+1; i++ {
        if intArr[i]%2 == 0 {
            fmt.Println(intArr[i])
        }
    }
}

Les exigences de la question originale sont traduites ci-dessous
1) La complexité temporelle est linéaire
2) La complexité spatiale est O(k)
3) La
complexité temporelle stable est O( n) , ce qui signifie que le tri par comparaison n'est plus possible. La meilleure complexité temporelle moyenne du tri par comparaison est O(nlgn), comme le tri rapide, etc.
C'est déjà une conclusion mathématiquement prouvée de "Introduction aux algorithmes".
Les seuls avec un temps linéaire sont le comptage, les seaux et les bases, voir https://www.byvoid.com/blog/sort-radix
, c'est-à-dire que le tri est uniquement
1) Comptage - complexité temporelle O(n) complexité spatiale O(k n )

http://www.geeksforgeeks.org/counting-sort/

2) Tri par buckets - O(n) complexité spatiale O(k n)
http://www.growingwiththeweb.com/2015/06/bucket-sort.html

3) Tri par base O(n) et O(n k)

Donc, personnellement, je pense que cette question n’a pas de solution.
BTW : je vous suggère de jeter un œil au lien ci-dessous
http://bigocheatsheet.com/

J'ai obtenu mon diplôme il y a longtemps, donc je ne me souviens pas très clairement de ces choses concluantes, ce qui signifie que je ne suis pas responsable des choses concluantes ci-dessus :-)
L'affiche peut fournir des preuves supplémentaires basées sur l'article ci-dessus.

Mais la complexité temporelle moyenne basée sur la comparaison ne dépasse pas O(nlogn). J'en suis sûr, il est donc recommandé de regarder parmi les trois radix, bucket sort et radix pour voir lequel est le plus proche du vôtre. exigences.

Voici une réponse à une question similaire :

https://www.quora.com/Given-an-array-of-integers-how-do-I-re-arrange-the-numbers-such-that-odd-numbers-occupy-odd-position-and-even-numbers-occupy-even-position

La solution à votre problème est la même, car il n'y a qu'une seule différence dans les exigences : les nombres impairs sont à des positions d'index impaires et les nombres pairs sont à des positions d'index paires. La première réponse dans le lien est la réponse la plus proche de ce que vous voulez. La raison pour laquelle elle est seulement proche est qu'elle nécessite que le tableau d'origine puisse accueillir une petite quantité de données supplémentaires.

En fait, je doute encore qu'il puisse y avoir des conditions implicites que l'intervieweur ne vous a pas expliquées clairement en vous posant des questions. Par exemple, si le tableau 2n lui-même est un tableau ordonné, la situation sera très différente.

Après avoir lu la question et y avoir brièvement réfléchi, l'idée est la suivante :

S'il s'agit du tableau donné, il n'y a aucun moyen de conserver l'ordre relatif inchangé. Le code suivant ne peut satisfaire que les conditions 2 et 3 :

for (i=0, j= 2n-1; i<n, j>n; ){
    if((n[i] % 2 == 1) && (n[j] % 2==0)){
        i++;
        j--;
    }
    
    if((n[i] % 2 == 0) && (n[j] % 2)==1){
           swap(n[i],n[j]);
           i++;
           j--;
    }
    
    if((n[i] %2 == 0) && (n[j] %2 == 0)){
        j--;
    }
    
    if((n[i] %2 == 1) && (n[j] %2 == 1)){
        i++;
    }
}

Vérifiez simplement depuis le début et la fin, et jugez chacune des quatre situations.

Si une liste chaînée est donnée, les trois conditions ci-dessus sont facilement remplies.

Un autre : on m'a marché dessus sans raison. . .

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

Voir l'explication pour tirer des conclusions à partir d'un exemple.

Le lien papier est le suivant

《PARTITIONNEMENT D'ESPACE MINIMUM STABLE EN TEMPS LINÉAIRE》

On dirait qu’il n’y a pas de solution.

Même cet article suppose que la comparaison de la valeur f de deux nombres est un temps constant. On peut comprendre que chaque nombre a sa propre information de position.
http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf

Ce qui suit est ma propre analyse de No Solution :

Cette séquence est un groupe de permutation. Nous savons que d'une séquence de longueur n à une autre séquence via une permutation par paire de nombres, jusqu'à n-1 opérations de permutation sont nécessaires. Le principe est que nous connaissons la permutation requise pour chaque nombre. .à l'emplacement. Cependant, comme il n'existe aucun moyen de connaître la position où chaque numéro doit être remplacé (il n'y a aucun endroit pour le stocker), il n'existe aucun moyen évident de trouver la position de remplacement de chaque numéro en temps constant (en fait, je préfère que cela n'existe pas) méthode). Cela ne devrait donc pas être possible.

Des tableaux auxiliaires peuvent être utilisés s'il y a de l'espace supplémentaire.
Si vous avez du temps supplémentaire, vous pouvez utiliser une méthode similaire au tri par fusion, implémentation non récursive, car elle ne divise que les impairs et les pairs et peut être échangée sur place.