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

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

Answer 2

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.

Answer 3

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...

Answer 4

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.

Answer 5

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])
        }
    }
}

Answer 6

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.

Answer 7

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.

Answer 8

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. . .

Answer 9

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》

Answer 10

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.