Finden Sie die kleinste Ganzzahl, die nicht in einer Liste enthalten ist

Eine interessante Interviewfrage, die ein Kollege von mir verwendet:

Angenommen, Sie erhalten eine sehr lange, unsortierte Liste vorzeichenloser 64-Bit-Ganzzahlen. Wie würden Sie die kleinste nicht negative Ganzzahl finden, die nicht in der Liste vorkommt?

FOLLOW-UP: Nachdem die offensichtliche Lösung durch Sortieren vorgeschlagen wurde, können Sie dies schneller als O (n log n) tun?

FOLLOW-UP: Ihr Algorithmus muss auf einem Computer mit beispielsweise 1 GB Speicher ausgeführt werden

ERKLÄRUNG: Die Liste befindet sich im RAM, obwohl sie möglicherweise eine große Menge davon verbraucht. Sie erhalten die Größe der Liste, z. B. N, im Voraus.

Wenn die Datenstruktur an Ort und Stelle mutiert werden kann und Direktzugriff unterstützt, können Sie dies in O (N) -Zeit und O (1) zusätzlichem Speicherplatz tun. Gehen Sie einfach nacheinander durch das Array und schreiben Sie für jeden Index den Wert am Index in den durch value angegebenen Index, platzieren Sie rekursiv einen Wert an dieser Stelle an seiner Stelle und werfen Sie Werte> N weg. Gehen Sie dann erneut durch das Array und suchen Sie nach dem Punkt Wobei der Wert nicht mit dem Index übereinstimmt - das ist der kleinste Wert, der nicht im Array enthalten ist. Dies führt zu höchstens 3N-Vergleichen und verwendet nur wenige Werte für temporären Speicherplatz.

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N

Hier ist eine einfache O(N)Lösung, die O(N)Platz benötigt. Ich gehe davon aus, dass wir die Eingabeliste auf nicht negative Zahlen beschränken und die erste nicht negative Zahl finden möchten, die nicht in der Liste enthalten ist.

1. Finden Sie die Länge der Liste; Sagen wir es ist N.
2. Ordnen Sie ein Array von NBooleschen Werten zu, die für alle initialisiert sind false.
3. Wenn für jede Zahl Xin der Liste Xkleiner als ist N, setzen Sie das X'thElement des Arrays auf true.
4. Scannen Sie das Array ausgehend vom Index 0und suchen Sie nach dem ersten Element false. Wenn Sie den ersten falseam Index finden I, Iist die Antwort. Andernfalls (dh wenn alle Elemente vorhanden sind true) lautet die Antwort N.

In der Praxis würde das "Array von NBooleschen Werten" wahrscheinlich als "Bitmap" oder "Bitset" codiert, das als byteoder intArray dargestellt wird. Dies benötigt normalerweise weniger Speicherplatz (abhängig von der Programmiersprache) und ermöglicht falseeine schnellere Suche nach dem ersten .

So / warum funktioniert der Algorithmus.

Angenommen, die NZahlen in der Liste sind nicht unterschiedlich oder eine oder mehrere von ihnen sind größer als N. Dies bedeutet, dass mindestens eine Nummer in dem Bereich vorhanden sein muss 0 .. N - 1, der nicht in der Liste enthalten ist. Das Problem, die kleinste fehlende Zahl zu finden, muss sich daher auf das Problem reduzieren, die kleinste fehlende Zahl kleiner als zu findenN . Dies bedeutet, dass wir keine Zahlen verfolgen müssen, die größer oder gleich sind N... weil sie nicht die Antwort sind.

Die Alternative zum vorherigen Absatz besteht darin, dass die Liste eine Permutation der Zahlen aus ist 0 .. N - 1. In diesem Fall setzt Schritt 3 alle Elemente des Arrays auf trueund Schritt 4 sagt uns, dass die erste "fehlende" Nummer ist N.

Die rechnerische Komplexität des Algorithmus ist O(N)mit einer relativ kleinen Proportionalitätskonstante verbunden. Es werden zwei lineare Durchgänge durch die Liste ausgeführt oder nur ein Durchgang, wenn bekannt ist, dass die Listenlänge damit beginnt. Es ist nicht erforderlich, das Halten der gesamten Liste im Speicher darzustellen, daher ist die asymptotische Speichernutzung des Algorithmus genau das, was zur Darstellung des Arrays von Booleschen Werten erforderlich ist. dh O(N)Bits.

(Im Gegensatz dazu setzen Algorithmen, die auf In-Memory-Sortierung oder -Partitionierung basieren, voraus, dass Sie die gesamte Liste im Speicher darstellen können. In der Form, in der die Frage gestellt wurde, wären dafür O(N)64-Bit-Wörter erforderlich .)

@Jorn kommentiert, dass die Schritte 1 bis 3 eine Variation der Zählsortierung sind. In gewissem Sinne hat er Recht, aber die Unterschiede sind signifikant:

• Eine Zählsortierung erfordert ein Array von (mindestens) Xmax - XminZählern, wobei Xmaxdie größte Zahl in der Liste und Xmindie kleinste Zahl in der Liste ist. Jeder Zähler muss in der Lage sein, N Zustände darzustellen; dh unter der Annahme einer binären Darstellung muss sie (mindestens) ganzzahlige ceiling(log2(N))Bits haben.
• Um die Arraygröße zu bestimmen, muss eine Zählsortierung einen ersten Durchgang durch die Liste machen, um Xmaxund zu bestimmen Xmin.
• Der minimale Platzbedarf im ungünstigsten Fall beträgt daher ceiling(log2(N)) * (Xmax - Xmin)Bits.

Im Gegensatz dazu erfordert der oben vorgestellte Algorithmus Nim schlimmsten und besten Fall einfach Bits.

Diese Analyse führt jedoch zu der Intuition, dass der Algorithmus, wenn er die Liste zunächst nach einer Null durchsucht (und bei Bedarf die Listenelemente zählt), eine schnellere Antwort ohne Leerzeichen geben würde, wenn er die Null findet. Es lohnt sich auf jeden Fall, dies zu tun, wenn eine hohe Wahrscheinlichkeit besteht, mindestens eine Null in der Liste zu finden. Und dieser zusätzliche Durchgang ändert nichts an der Gesamtkomplexität.

BEARBEITEN: Ich habe die Beschreibung des Algorithmus geändert, um "Array von Booleschen Werten" zu verwenden, da die Leute meine ursprüngliche Beschreibung mit Bits und Bitmaps anscheinend als verwirrend empfanden.

Da das OP jetzt festgelegt hat, dass die ursprüngliche Liste im RAM gespeichert ist und der Computer nur beispielsweise 1 GB Speicher hat, werde ich mich auf die Probe stellen und vorhersagen, dass die Antwort Null ist.

1 GB RAM bedeutet, dass die Liste höchstens 134.217.728 Nummern enthalten kann. Es gibt jedoch 2 ⁶⁴ = 18.446.744.073.709.551.616 mögliche Zahlen. Die Wahrscheinlichkeit, dass Null in der Liste steht, beträgt 1 zu 137.438.953.472.

Im Gegensatz dazu ist meine Wahrscheinlichkeit, dieses Jahr vom Blitz getroffen zu werden, 1 zu 700.000. Und meine Wahrscheinlichkeit , von einem Meteoriten getroffen zu werden, liegt bei 1 zu 10 Billionen. Daher ist es ungefähr zehnmal wahrscheinlicher, dass ich aufgrund meines vorzeitigen Todes durch ein Himmelsobjekt in eine wissenschaftliche Zeitschrift geschrieben werde, als dass die Antwort nicht Null ist.

Wie in anderen Antworten erwähnt, können Sie eine Sortierung durchführen und dann einfach nach oben scannen, bis Sie eine Lücke finden.

Sie können die algorithmische Komplexität auf O (N) verbessern und den O (N) -Raum beibehalten, indem Sie einen modifizierten QuickSort verwenden, bei dem Sie Partitionen entfernen, die keine potenziellen Kandidaten für das Eindämmen der Lücke sind.

• Entfernen Sie in der ersten Partitionsphase Duplikate.
• Überprüfen Sie nach Abschluss der Partitionierung die Anzahl der Elemente in der unteren Partition
• Entspricht dieser Wert dem Wert, der zum Erstellen der Partition verwendet wird?
  • Wenn ja, bedeutet dies, dass sich die Lücke in der höheren Partition befindet.
    • Fahren Sie mit dem Quicksort fort und ignorieren Sie die untere Partition
  • Ansonsten befindet sich die Lücke in der unteren Partition
    • Fahren Sie mit dem Quicksort fort und ignorieren Sie die höhere Partition

Dies spart eine große Anzahl von Berechnungen.

Da die Zahlen alle 64 Bit lang sind, können wir eine Radix-Sortierung verwenden , die O (n) ist. Sortieren Sie sie und scannen Sie sie, bis Sie das finden, wonach Sie suchen.

Wenn die kleinste Zahl Null ist, scannen Sie vorwärts, bis Sie eine Lücke finden. Wenn die kleinste Zahl nicht Null ist, ist die Antwort Null.

Um eine der Fallstricke des O(N)Denkens zu veranschaulichen , ist hier ein O(N)Algorithmus, der O(1)Raum verwendet.

for i in [0..2^64):
  if i not in list: return i

print "no 64-bit integers are missing"

Für eine platzsparende Methode und alle Werte sind unterschiedlich. Sie können dies räumlich O( k )und zeitlich tun O( k*log(N)*N ). Es ist platzsparend und es werden keine Daten verschoben und alle Operationen sind elementar (Hinzufügen von Subtrahieren).

1. einstellen U = N; L=0
2. Partitionieren Sie zuerst den Nummernraum in kRegionen. So was:
   • 0->(1/k)*(U-L) + L, 0->(2/k)*(U-L) + L, 0->(3/k)*(U-L) + L...0->(U-L) + L
3. Finden Sie heraus, wie viele Zahlen ( count{i}) sich in jeder Region befinden. ( N*kSchritte)
4. Suchen Sie die erste Region ( h), die nicht voll ist. Das heißt count{h} < upper_limit{h}. ( kSchritte)
5. wenn h - count{h-1} = 1du deine Antwort hast
6. einstellen U = count{h}; L = count{h-1}
7. gehe zu 2

Dies kann durch Hashing verbessert werden (danke für Nic diese Idee).

1. gleich
2. Partitionieren Sie zuerst den Nummernraum in kRegionen. So was:
   • L + (i/k)->L + (i+1/k)*(U-L)
3. inc count{j} mit j = (number - L)/k (if L < number < U)
4. Finde die erste Region ( h), die keine k Elemente enthält
5. wenn count{h} = 1h deine Antwort ist
6. einstellen U = maximum value in region h L = minimum value in region h

Dies wird in laufen O(log(N)*N).

Ich würde sie einfach sortieren und dann die Sequenz durchlaufen, bis ich eine Lücke finde (einschließlich der Lücke am Anfang zwischen Null und der ersten Zahl).

In Bezug auf einen Algorithmus würde so etwas es tun:

def smallest_not_in_list(list):
    sort(list)
    if list[0] != 0:
        return 0
    for i = 1 to list.last:
        if list[i] != list[i-1] + 1:
            return list[i-1] + 1
    if list[list.last] == 2^64 - 1:
        assert ("No gaps")
    return list[list.last] + 1

Wenn Sie viel mehr Speicher als CPU-Grunzen haben, können Sie natürlich eine Bitmaske aller möglichen 64-Bit-Werte erstellen und einfach die Bits für jede Zahl in der Liste setzen. Suchen Sie dann nach dem ersten 0-Bit in dieser Bitmaske. Das macht es zu einer O (n) -Operation in Bezug auf die Zeit, aber verdammt teuer in Bezug auf den Speicherbedarf :-)

Ich bezweifle, dass Sie O (n) verbessern können, da ich keinen Weg sehe, dies zu tun, bei dem nicht jede Zahl mindestens einmal betrachtet wird.

Der Algorithmus für diesen wäre wie folgt:

def smallest_not_in_list(list):
    bitmask = mask_make(2^64) // might take a while :-)
    mask_clear_all (bitmask)
    for i = 1 to list.last:
        mask_set (bitmask, list[i])
    for i = 0 to 2^64 - 1:
        if mask_is_clear (bitmask, i):
            return i
    assert ("No gaps")

Sortieren Sie die Liste, sehen Sie sich das erste und das zweite Element an und gehen Sie nach oben, bis eine Lücke vorhanden ist.

Sie können dies in O (n) Zeit und O (1) zusätzlichem Raum tun, obwohl der versteckte Faktor ziemlich groß ist. Dies ist kein praktischer Weg, um das Problem zu lösen, aber es könnte trotzdem interessant sein.

Durchlaufen Sie für jede vorzeichenlose 64-Bit-Ganzzahl (in aufsteigender Reihenfolge) die Liste, bis Sie die Ziel-Ganzzahl finden oder das Ende der Liste erreichen. Wenn Sie das Ende der Liste erreichen, ist die Ziel-Ganzzahl die kleinste Ganzzahl, die nicht in der Liste enthalten ist. Wenn Sie das Ende der 64-Bit-Ganzzahlen erreichen, befindet sich jede 64-Bit-Ganzzahl in der Liste.

Hier ist es als Python-Funktion:

def smallest_missing_uint64(source_list):
    the_answer = None

    target = 0L
    while target < 2L**64:

        target_found = False
        for item in source_list:
            if item == target:
                target_found = True

        if not target_found and the_answer is None:
            the_answer = target

        target += 1L

    return the_answer

Diese Funktion ist absichtlich ineffizient, um O (n) zu halten. Beachten Sie insbesondere, dass die Funktion die Ziel-Ganzzahlen auch dann überprüft, wenn die Antwort gefunden wurde. Wenn die Funktion zurückgegeben würde, sobald die Antwort gefunden wurde, würde die Häufigkeit, mit der die äußere Schleife ausgeführt wurde, durch die Größe der Antwort gebunden, die durch n gebunden ist. Diese Änderung würde die Laufzeit O (n ^ 2) machen, obwohl sie viel schneller wäre.

Vielen Dank an egon, swilden und Stephen C für meine Inspiration. Erstens kennen wir die Grenzen des Zielwerts, da dieser nicht größer als die Größe der Liste sein kann. Außerdem könnte eine 1-GB-Liste höchstens 134217728 (128 * 2 ^ 20) 64-Bit-Ganzzahlen enthalten.

Hashing-Teil
Ich schlage vor, Hashing zu verwenden, um unseren Suchraum drastisch zu reduzieren. Zuerst Quadratwurzel die Größe der Liste. Für eine 1-GB-Liste ist das N = 11.586. Richten Sie ein ganzzahliges Array der Größe N ein. Durchlaufen Sie die Liste und nehmen Sie die Quadratwurzel * jeder gefundenen Zahl als Hash. Erhöhen Sie in Ihrer Hash-Tabelle den Zähler für diesen Hash. Als nächstes durchlaufen Sie Ihre Hash-Tabelle. Der erste Bucket, den Sie finden, der nicht der maximalen Größe entspricht, definiert Ihren neuen Suchbereich.

Bitmap-Teil Richten Sie
nun eine reguläre Bitmap ein, die der Größe Ihres neuen Suchraums entspricht, und durchlaufen Sie die Quellliste erneut. Füllen Sie die Bitmap aus, sobald Sie jede Nummer in Ihrem Suchraum finden. Wenn Sie fertig sind, gibt Ihnen das erste nicht gesetzte Bit in Ihrer Bitmap Ihre Antwort.

Dies wird in O (n) Zeit und O (sqrt (n)) Raum abgeschlossen.

(* Sie könnten so etwas wie Bitverschiebung verwenden, um dies viel effizienter zu tun, und einfach die Anzahl und Größe der Eimer entsprechend variieren.)

Wenn in einer Liste von Zahlen nur eine Zahl fehlt, können Sie die fehlende Zahl am einfachsten ermitteln, indem Sie die Reihen summieren und jeden Wert in der Liste subtrahieren. Der Endwert ist die fehlende Zahl.

 int i = 0;
            while ( i < Array.Length)
            {

                if (Array[i] == i + 1)
                {
                    i++;
                }

                if (i < Array.Length)
                {
                    if (Array[i] <= Array.Length)
                    {//SWap

                        int temp = Array[i];
                        int AnoTemp = Array[temp - 1];
                        Array[temp - 1] = temp;
                        Array[i] = AnoTemp;

                    }
                    else
                       i++;



                }
            }

            for (int j = 0; j < Array.Length; j++)
            {
                if (Array[j] > Array.Length)
                {
                    Console.WriteLine(j + 1);
                    j = Array.Length;
                }
                else
                    if (j == Array.Length - 1)
                        Console.WriteLine("Not Found !!");

            }
        }

Wir könnten eine Hash-Tabelle verwenden, um die Zahlen zu speichern. Sobald alle Zahlen fertig sind, führen Sie einen Zähler von 0 aus, bis wir den niedrigsten finden. Ein einigermaßen guter Hash wird in konstanter Zeit gehasht und gespeichert und in konstanter Zeit abgerufen.

for every i in X         // One scan Θ(1)
   hashtable.put(i, i);  // O(1)

low = 0;

while (hashtable.get(i) <> null)   // at most n+1 times
   low++;

print low;

Der schlimmste Fall, wenn sich nElemente im Array befinden {0, 1, ... n-1}und in diesem Fall die Antwort erhalten wird n, wobei diese weiterhin beibehalten wird O(n).

Hier ist meine Antwort in Java geschrieben:

Grundidee: 1- Durchlaufen Sie das Array und werfen Sie doppelte positive, Nullen und negative Zahlen weg, während Sie den Rest zusammenfassen, die maximale positive Zahl erhalten und die eindeutigen positiven Zahlen in einer Karte behalten.

2- Berechnen Sie die Summe als max * (max + 1) / 2.

3- Ermitteln Sie die Differenz zwischen den in den Schritten 1 und 2 berechneten Beträgen

4- Wiederholen Sie die Schleife von 1 bis zum Minimum von [Summen Differenz, max] und geben Sie die erste Zahl zurück, die nicht in der in Schritt 1 aufgefüllten Karte enthalten ist.

public static int solution(int[] A) {
    if (A == null || A.length == 0) {
        throw new IllegalArgumentException();
    }

    int sum = 0;
    Map<Integer, Boolean> uniqueNumbers = new HashMap<Integer, Boolean>();
    int max = A[0];
    for (int i = 0; i < A.length; i++) {
        if(A[i] < 0) {
            continue;
        }
        if(uniqueNumbers.get(A[i]) != null) {
            continue;
        }
        if (A[i] > max) {
            max = A[i];
        }
        uniqueNumbers.put(A[i], true);
        sum += A[i];
    }
    int completeSum = (max * (max + 1)) /  2;
    for(int j = 1; j <= Math.min((completeSum - sum), max); j++) {
        if(uniqueNumbers.get(j) == null) { //O(1)
            return j;
        }
    }
    //All negative case
    if(uniqueNumbers.isEmpty()) {
        return 1;
    }
    return 0;
}

Wie Stephen C klug hervorhob, muss die Antwort eine Zahl sein, die kleiner als die Länge des Arrays ist. Ich würde dann die Antwort durch binäre Suche finden. Dies optimiert den schlimmsten Fall (sodass der Interviewer Sie in einem pathologischen "Was wäre wenn" -Szenario nicht fangen kann). Weisen Sie in einem Interview darauf hin, dass Sie dies tun, um für den schlimmsten Fall zu optimieren.

Die Verwendung der binären Suche besteht darin, die gesuchte Zahl von jedem Element des Arrays zu subtrahieren und nach negativen Ergebnissen zu suchen.

Ich mag die "Rate Null" Apprach. Wenn die Zahlen zufällig waren, ist Null sehr wahrscheinlich. Wenn der "Prüfer" eine nicht zufällige Liste erstellt hat, fügen Sie eine hinzu und raten Sie erneut:

LowNum=0
i=0
do forever {
  if i == N then leave /* Processed entire array */
  if array[i] == LowNum {
     LowNum++
     i=0
     }
   else {
     i++
   }
}
display LowNum

Der schlimmste Fall ist n * N mit n = N, aber in der Praxis ist n höchstwahrscheinlich eine kleine Zahl (z. B. 1).

Ich bin mir nicht sicher, ob ich die Frage habe. Wenn jedoch für Liste 1,2,3,5,6 die fehlende Zahl 4 ist, kann die fehlende Zahl in O (n) gefunden werden durch: (n + 2) (n + 1) / 2- (n + 1) n / 2

EDIT: Entschuldigung, ich denke ich habe letzte Nacht zu schnell nachgedacht. Wie auch immer, der zweite Teil sollte eigentlich durch Summe (Liste) ersetzt werden, woher O (n) kommt. Die Formel enthüllt die Idee dahinter: Für n aufeinanderfolgende ganze Zahlen sollte die Summe (n + 1) * n / 2 sein. Wenn eine Zahl fehlt, entspricht die Summe der Summe der (n + 1) aufeinanderfolgenden ganzen Zahlen abzüglich der fehlenden Zahl.

Vielen Dank, dass Sie darauf hingewiesen haben, dass ich einige Mittelstücke in meinem Kopf hatte.

Gut gemacht Ants Aasma! Ich dachte ungefähr 15 Minuten lang über die Antwort nach und fand unabhängig eine Antwort in einer ähnlichen Denkweise wie Ihre:

#define SWAP(x,y) { numerictype_t tmp = x; x = y; y = tmp; }
int minNonNegativeNotInArr (numerictype_t * a, size_t n) {
    int m = n;
    for (int i = 0; i < m;) {
        if (a[i] >= m || a[i] < i || a[i] == a[a[i]]) {
            m--;
            SWAP (a[i], a[m]);
            continue;
        }
        if (a[i] > i) {
            SWAP (a[i], a[a[i]]);
            continue;
        }
        i++;
    }
    return m;
}

m steht für "die aktuell maximal mögliche Ausgabe, wenn ich weiß, was ich über die ersten i-Eingaben weiß und bis zum Eintrag bei m-1 nichts anderes über die Werte annehme".

Dieser Wert von m wird nur zurückgegeben, wenn (a [i], ..., a [m-1]) eine Permutation der Werte (i, ..., m-1) ist. Wenn also a [i]> = m oder wenn a [i] <i oder wenn a [i] == a [a [i]] ist, wissen wir, dass m die falsche Ausgabe ist und mindestens ein Element niedriger sein muss. Wenn wir also m dekrementieren und a [i] gegen a [m] tauschen, können wir rekursieren.

Wenn dies nicht wahr ist, sondern ein [i]> i, dann wissen wir, dass a [i]! = A [a [i]], dass das Austauschen eines [i] gegen ein [a [i]] die Anzahl der Elemente erhöht an ihrem eigenen Platz.

Andernfalls muss a [i] gleich i sein. In diesem Fall können wir i inkrementieren, da wir wissen, dass alle Werte von bis einschließlich dieses Index gleich ihrem Index sind.

Der Beweis, dass dies nicht in eine Endlosschleife eintreten kann, bleibt dem Leser als Übung überlassen. :) :)

Das Dafny- Fragment aus Ants 'Antwort zeigt, warum der In-Place-Algorithmus möglicherweise fehlschlägt. Die requiresVorbedingung beschreibt, dass die Werte jedes Elements nicht über die Grenzen des Arrays hinausgehen dürfen.

method AntsAasma(A: array<int>) returns (M: int)
  requires A != null && forall N :: 0 <= N < A.Length ==> 0 <= A[N] < A.Length;
  modifies A; 
{
  // Pass 1, move every value to the position of its value
  var N := A.Length;
  var cursor := 0;
  while (cursor < N)
  {
    var target := A[cursor];
    while (0 <= target < N && target != A[target])
    {
        var new_target := A[target];
        A[target] := target;
        target := new_target;
    }
    cursor := cursor + 1;
  }

  // Pass 2, find first location where the index doesn't match the value
  cursor := 0;
  while (cursor < N)
  {
    if (A[cursor] != cursor)
    {
      return cursor;
    }
    cursor := cursor + 1;
  }
  return N;
}

Fügen Sie den Code mit und ohne forall ...Klausel in den Validator ein , um den Überprüfungsfehler anzuzeigen. Der zweite Fehler ist darauf zurückzuführen, dass der Prüfer keine Beendigungsbedingung für die Pass 1-Schleife festlegen kann. Dies zu beweisen, bleibt jemandem überlassen, der das Tool besser versteht.

Hier ist eine Antwort in Java, die die Eingabe nicht ändert und O (N) -Zeit und N Bits sowie einen kleinen konstanten Speicheraufwand verwendet (wobei N die Größe der Liste ist):

int smallestMissingValue(List<Integer> values) {
    BitSet bitset = new BitSet(values.size() + 1);
    for (int i : values) {
        if (i >= 0 && i <= values.size()) {
            bitset.set(i);
        }
    }
    return bitset.nextClearBit(0);
}

def solution(A):

index = 0
target = []
A = [x for x in A if x >=0]

if len(A) ==0:
    return 1

maxi = max(A)
if maxi <= len(A):
    maxi = len(A)

target = ['X' for x in range(maxi+1)]
for number in A:
    target[number]= number

count = 1
while count < maxi+1:
    if target[count] == 'X':
        return count
    count +=1
return target[count-1] + 1

Erhielt 100% für die obige Lösung.

1) Negativ und Null filtern

2) Sortieren / unterscheiden

3) Array besuchen

Komplexität : O (N) oder O (N * log (N))

mit Java8

public int solution(int[] A) {
            int result = 1;
    boolean found = false;
    A = Arrays.stream(A).filter(x -> x > 0).sorted().distinct().toArray();
    //System.out.println(Arrays.toString(A));
    for (int i = 0; i < A.length; i++) {
        result = i + 1;
        if (result != A[i]) {
            found = true;
            break;
        }
    }
    if (!found && result == A.length) {
        //result is larger than max element in array
        result++;
    }
    return result;
}

Ein ungeordnetes_Set kann verwendet werden, um alle positiven Zahlen zu speichern. Anschließend können wir von 1 bis zur Länge des ungeordneten_Sets iterieren und die erste Zahl sehen, die nicht vorkommt.

int firstMissingPositive(vector<int>& nums) {

    unordered_set<int> fre;
    // storing each positive number in a hash.
    for(int i = 0; i < nums.size(); i +=1)
    {
        if(nums[i] > 0)
            fre.insert(nums[i]);
     }

    int i = 1;
    // Iterating from 1 to size of the set and checking 
    // for the occurrence of 'i'

    for(auto it = fre.begin(); it != fre.end(); ++it)
    {
        if(fre.find(i) == fre.end())
            return i;
        i +=1;
    }

    return i;
}

Lösung durch einfaches Javascript

var a = [1, 3, 6, 4, 1, 2];

function findSmallest(a) {
var m = 0;
  for(i=1;i<=a.length;i++) {
    j=0;m=1;
    while(j < a.length) {
      if(i === a[j]) {
        m++;
      }
      j++;
    }
    if(m === 1) {
      return i;
    }
  }
}

console.log(findSmallest(a))

Hoffe das hilft jemandem.

Mit Python ist es nicht das effizienteste, aber richtig

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import datetime

# write your code in Python 3.6

def solution(A):
    MIN = 0
    MAX = 1000000
    possible_results = range(MIN, MAX)

    for i in possible_results:
        next_value = (i + 1)
        if next_value not in A:
            return next_value
    return 1

test_case_0 = [2, 2, 2]
test_case_1 = [1, 3, 44, 55, 6, 0, 3, 8]
test_case_2 = [-1, -22]
test_case_3 = [x for x in range(-10000, 10000)]
test_case_4 = [x for x in range(0, 100)] + [x for x in range(102, 200)]
test_case_5 = [4, 5, 6]
print("---")
a = datetime.datetime.now()
print(solution(test_case_0))
print(solution(test_case_1))
print(solution(test_case_2))
print(solution(test_case_3))
print(solution(test_case_4))
print(solution(test_case_5))

def solution(A):
    A.sort()
    j = 1
    for i, elem in enumerate(A):
        if j < elem:
            break
        elif j == elem:
            j += 1
            continue
        else:
            continue
    return j

das kann helfen:

0- A is [5, 3, 2, 7];
1- Define B With Length = A.Length;                            (O(1))
2- initialize B Cells With 1;                                  (O(n))
3- For Each Item In A:
        if (B.Length <= item) then B[Item] = -1                (O(n))
4- The answer is smallest index in B such that B[index] != -1  (O(n))