Finden Sie die erste fehlende positive ganze Zahl in Python

Question

Ich habe folgende Aufgabe:

eine unsortierte Integer-Array, finden die erste fehlende positive ganze Zahl gegeben. Ihr Algorithmus sollte in O (n) Zeit laufen und konstanten Speicherplatz verwenden.

Nach einigem Nachdenken und einen Hinweis bekommen, habe ich beschlossen, den Code finden Sie die Eingabeliste A. Die sich ändern:

def firstMissingPositive(A): 
     m=max(A) 
     ln=len(A) 
     i=0 
     while i<ln: 
      if A[i]>=1 and A[i]<=ln: 
       if A[A[i]-1]!=m+1: 

        A[A[i]-1], A[i] = m+1, A[A[i]-1] 
       else: 
        i+=1 

      else: 
       i+=1 
     for i in range(ln): 
      if A[i]!=m+1: 
       return i+1 

Wenn ich es laufen, dauert es eine lange Zeit. Was soll ich tun, um es ein bisschen schneller zu machen?

EDIT: Hier ist die Liste A.

A=[ 417, 929, 845, 462, 675, 175, 73, 867, 14, 201, 777, 407, 80, 882, 785, 563, 209, 261, 776, 362, 730, 74, 649, 465, 353, 801, 503, 154, 998, 286, 520, 692, 68, 805, 835, 210, 819, 341, 564, 215, 984, 643, 381, 793, 726, 213, 866, 706, 97, 538, 308, 797, 883, 59, 328, 743, 694, 607, 729, 821, 32, 672, 130, 13, 76, 724, 384, 444, 884, 192, 917, 75, 551, 96, 418, 840, 235, 433, 290, 954, 549, 950, 21, 711, 781, 132, 296, 44, 439, 164, 401, 505, 923, 136, 317, 548, 787, 224, 23, 185, 6, 350, 822, 457, 489, 133, 31, 830, 386, 671, 999, 255, 222, 944, 952, 637, 523, 494, 916, 95, 734, 908, 90, 541, 470, 941, 876, 264, 880, 761, 535, 738, 128, 772, 39, 553, 656, 603, 868, 292, 117, 966, 259, 619, 836, 818, 493, 592, 380, 500, 599, 839, 268, 67, 591, 126, 773, 635, 800, 842, 536, 668, 896, 260, 664, 506, 280, 435, 618, 398, 533, 647, 373, 713, 745, 478, 129, 844, 640, 886, 972, 62, 636, 79, 600, 263, 52, 719, 665, 376, 351, 623, 276, 66, 316, 813, 663, 831, 160, 237, 567, 928, 543, 508, 638, 487, 234, 997, 307, 480, 620, 890, 216, 147, 271, 989, 872, 994, 488, 291, 331, 8, 769, 481, 924, 166, 89, 824, -4, 590, 416, 17, 814, 728, 18, 673, 662, 410, 727, 667, 631, 660, 625, 683, 33, 436, 930, 91, 141, 948, 138, 113, 253, 56, 432, 744, 302, 211, 262, 968, 945, 396, 240, 594, 684, 958, 343, 879, 155, 395, 288, 550, 482, 557, 826, 598, 795, 914, 892, 690, 964, 981, 150, 179, 515, 205, 265, 823, 799, 190, 236, 24, 498, 229, 420, 753, 936, 191, 366, 935, 434, 311, 920, 167, 817, 220, 219, 741, -2, 674, 330, 909, 162, 443, 412, 974, 294, 864, 971, 760, 225, 681, 689, 608, 931, 427, 687, 466, 894, 303, 390, 242, 339, 252, 20, 218, 499, 232, 184, 490, 4, 957, 597, 477, 354, 677, 691, 25, 580, 897, 542, 186, 359, 346, 409, 655, 979, 853, 411, 344, 358, 559, 765, 383, 484, 181, 82, 514, 582, 593, 77, 228, 921, 348, 453, 274, 449, 106, 657, 783, 782, 811, 333, 305, 784, 581, 746, 858, 249, 479, 652, 270, 429, 614, 903, 102, 378, 575, 119, 196, 12, 990, 356, 277, 169, 70, 518, 282, 676, 137, 622, 616, 357, 913, 161, 3, 589, 327 ] 

Answer 1

nicht die vollständige Ursache für lange Laufzeiten sein, aber ich habe einen Fehler finden, die eine Endlosschleife verursachen. Ich begann durch zufälliges Integer Arrays von Länge zu schaffen 20.

a = [random.randint(-10, 20) for _ in range(20)] 

Added zwei print-Anweisungen, um zu sehen, was geschieht.

while i<ln: 
     print(A) 
     if A[i]>=1 and A[i]<=ln: 
      if A[A[i]-1]!=m+1: 
       print("Swapping %d"%i) 
       A[A[i]-1], A[i] = m+1, A[A[i]-1] 
      else: 
     ... 

Mit diesem Array als Eingabe Sie in eine Endlosschleife bekommen:

a = [-6, 3, 10, 14, 17, 6, 14, 1, -5, -8, 8, 15, 17, -10, 2, 7, 11, 2, 7, 11] 

>>> 
... 
[18, 18, -8, -10, -6, 6, 14, 18, -5, 18, 18, 15, 17, 18, 2, 7, 18, 18, 7, 11] 
Swapping 5 
[18, 18, -8, -10, -6, 6, 14, 18, -5, 18, 18, 15, 17, 18, 2, 7, 18, 18, 7, 11] 
Swapping 5 
[18, 18, -8, -10, -6, 6, 14, 18, -5, 18, 18, 15, 17, 18, 2, 7, 18, 18, 7, 11] 
... 

Es stellte sich heraus, dass, wenn A[A[i]-1] gleich A[i] dann Sie immer die gleiche Anzahl bis Ende setzen zurück in A[i]. In diesem Fall i == 5, A[5] == 6 und A[A[i]-1] == 6. In dieser Aussage,

A[A[i]-1], A[i] = m+1, A[A[i]-1] 

Die rechte Seite wird ausgewertet; m+1 ist A[5] zugewiesen; dann wird 6 A[5] zugewiesen. Ich reparierte es für diesen einen Fall durch die Zuweisungsreihenfolge tauschen:

A[i], A[A[i]-1] = A[A[i]-1], m+1 

---

Mit der Liste, die Sie auf die Frage hinzugefügt, ist es nun ein Indexerror mit meinem mod wirft. Obwohl die rechte Seite zuerst ausgewertet wird, scheint es, dass A[A[i]-1] auf der linken Seite nicht ausgewertet wird, bis nach die erste Zuweisung erfolgt ist und eine große Anzahl platziert in A[i] platziert wurde.

Rob's solution plagiiert - bewerten [A[i]-1 bevor Swaps vorgenommen werden:

def firstMissingPositive(A): 
    m=max(A) 
    ln=len(A) 
    print('max:{}, len:{}'.format(m, ln)) 
    i=0 
    while i<ln: 
##  print(A[:20]) 
     if A[i]>=1 and A[i]<=ln: 
      if A[A[i]-1]!=m+1: 
##    print("Swapping %d"%i) 
       v = A[i]-1 
       A[i], A[v] = A[v], m+1 
      else: 
       i+=1 
     else: 
      i+=1 
    for i in range(ln): 
     if A[i]!=m+1: 
      return i+1 

---

Und es immer noch gibt manchmal ein falsches Ergebnis so minus eins für mich.Es erzeugt falsche Ergebnisse für die folgenden:

[18, 2, 13, 3, 3, 0, 14, 1, 18, 12, 6, -1, -3, 15, 11, 13, -8, 7, -8, -7] 
[-6, 3, 10, 14, 17, 6, 14, 1, -5, -8, 8, 15, 17, -10, 2, 7, 11, 2, 7, 11] 
[7, -7, 19, 6, -3, -6, 1, -8, -1, 19, -8, 2, 4, 19, 5, 6, 6, 18, 8, 17] 

Answer 2

FWIW, hier ist, wie ich es tat:

def firstMissingPositive(A): 
    for i in range(len(A)): 
     while A[i] != i+1 and 0 < A[i] < len(A): 
      value = A[i]-1 
      A[i], A[value] = A[value], A[i] 
    for i, value in enumerate(A, 1): 
     if i != value: 
      return i 
    return len(A)+1 

assert firstMissingPositive([1,4,3,6,5]) == 2 
assert firstMissingPositive([1,44,3,66,55]) == 2 
assert firstMissingPositive([1,2,3,4,5]) == 6 
assert firstMissingPositive(A) == 1 

Answer 3

Blick zu mir, dass es sowohl in O (n) und konstanten Raum zu tun ist eine Art unmöglich. (I korrigiert Ständer, die Verbindung von Rockybilly gibt solche Lösung)

es in konstantem Raum man zu tun ist eine Art, die Liste zu sortieren gezwungen, und das ist O (n log n) für die meisten Sortieralgorithmen, und die hier sieht aus wie Einfügemarke, die im Durchschnitt O (n)

Also FWIW Ich entscheide mich, den konstanten Raum zu verwerfen, um es so nahe an O (n) zu tun, wie ich mir vorstellen kann mir eine 2n-Lösung (im schlimmsten Fall, im Durchschnitt ist n + k) (was in großen O-Notation ist immer noch O (n))

(Version 2 unten)

I set(sequence) genutzt haben könnte, und max(sequence) aber beide sind O (n), so dass ich kombinierte sich in der gleichen Schleife, und ich verwende set aus zwei Gründen: erstens eine mögliche Reduktion im Raum durch das Ignorieren von Duplikaten und auf dieselbe Weise interessiere ich mich nur für eine Zahl größer oder gleich meiner unteren Grenze (die ich auch generisch mache) und die zweite ist für die O (1) Mitgliedschaftstests.

Die letzte Zeile ist eine einfache lineare Suche nach dem fehlenden Elemente mit der Eigenschaft, die Standardeinstellung, wenn das maximale Element zu beginnen ist, niedriger zu starten oder die maximale + 1, wenn das Array kein fehlendes Element zwischen Start und ihrem Maximum hat.

sind hier einige Tests borgen von den anderen Antworten ...

assert 1 == firstMissingSince(A) 
assert 2 == firstMissingSince([1,4,3,6,5]) 
assert 2 == firstMissingSince([1,44,3,66,55]) 
assert 6 == firstMissingSince([1,2,3,4,5]) 
assert 4 == firstMissingSince([-6, 3, 10, 14, 17, 6, 14, 1, -5, -8, 8, 15, 17, -10, 2, 7, 11, 2, 7, 11]) 
assert 4 == firstMissingSince([18, 2, 13, 3, 3, 0, 14, 1, 18, 12, 6, -1, -3, 15, 11, 13, -8, 7, -8, -7]) 
assert 4 == firstMissingSince([-6, 3, 10, 14, 17, 6, 14, 1, -5, -8, 8, 15, 17, -10, 2, 7, 11, 2, 7, 11]) 
assert 3 == firstMissingSince([7, -7, 19, 6, -3, -6, 1, -8, -1, 19, -8, 2, 4, 19, 5, 6, 6, 18, 8, 17]) 

---

die Antwort von Rockybilly mich erkennen, dass ich brauche gar nicht den maximalen Wert kennen, so Hier ist Version 2

from itertools import count 

def firstMissingSince(sequence, start=1): 
    uniques = set(sequence) # { x for x in sequence if x>=start } 
    return next(x for x in count(start) if x not in uniques) 

Answer 4

Hier ist meine Lösung.

from collections import defaultdict 

def firstMissingPositive(A): 

    d = defaultdict(int) 
    for i in A: 
     d[i] = 1 

    j = 1 
    while True: 
     if d[j] == 0: 
      return j 
     j += 1 

Raum Komplexität: O (n)

Zeitkomplexität: O (n + k). Welches gilt als O (n). Hash-Komplexität wurde ebenfalls ignoriert.

---

By the way:Googling gibt die Antwort, die Sie, konstanter Raum und O (n) Zeit suchen.