Finde die erste fehlende Nummer in einer Zahlenfolge

7

Ich versuche herauszufinden, wie man die erste fehlende Zahl einer Folge von Zahlen wie dieser findet (1,2,3,5,6,9,10,15)

Ich möchte die erste fehlende Zahl, # 4, in eine Variable für die spätere Verwendung einfügen, weiß aber nicht wie?

Ich habe es versucht, aber das gibt mir nur die letzte Nummer:

%Vor%

Zuerst gibt es mir die erste Zahl nach einem "Loch" in der Zahlenfolge, zweitens alarmiert es weiterhin alle Zahlen, die nach einem "Loch" kommen, wenn ich keine Pause einlege. Ich will nur die erste fehlende Zahl einer Zahlenfolge von 1 - 32. Wie mache ich das?

Ich hoffe auf Hilfe und danke im Voraus; -)

    
Mansa 17.09.2013, 14:59
quelle

8 Antworten

10

Wie wäre es damit?

%Vor%     
Gowsikan 17.09.2013, 15:17
quelle
6

Die O (n) Lösungen sind einfach , aber das ist eine häufige Interviewfrage und oft suchen wir nach O (log n) Zeitlösung. Hier ist der JavaScript-Code. Es ist im Grunde eine modifizierte binäre Suche.

%Vor%

Ausgabe

%Vor%     
sapy 16.10.2016 05:35
quelle
3

Nach if(mynumbers[i] - mynumbers[i-1] != 1) , meinst du, die Serie wird immer um 1 erhöht?

%Vor%     
Paul S. 17.09.2013 15:07
quelle
1

Du wirst die Pause brauchen, egal was passiert. Dafür ist es da; um zu verhindern, dass die Schleife bis zum Ende fortgesetzt wird. Und Sie sollten die Länge des Arrays anstelle von Hardcoding 32 als Endbedingung verwenden, da Ihre Zahlen nur bis 32 gehen, aber es gibt möglicherweise Löcher in der Liste, so dass es nicht 32 Elemente im Array geben wird.

Da Sie wissen, dass jedes Element 1 mehr als das vorherige Element sein sollte, ist die Zahl im Loch eindeutig mynumbers[i - 1] + 1 .

%Vor%

BEARBEITEN: Dies gilt nur, wenn die fehlende Zahl nicht 1 ist. Um das zu erfassen, müssen Sie if (mynumbers[0] != 1)

überprüfen     
jonhopkins 17.09.2013 15:06
quelle
1

Bearbeiten:

%Vor% %Vor%

Wenn Sie es so machen, ist es einfach, es in einer Variablen zu speichern:

%Vor%     
Jeff Shaver 17.09.2013 15:07
quelle
1
%Vor%

Diese Lösung funktioniert für ein Array von positiven Zahlen.

    
tourniquet 25.12.2017 00:18
quelle
0

Eine Lösung, die array.reduce verwendet

%Vor%

Und hier sind einige Testfälle:

%Vor%     
Rahul Gaba 12.04.2018 18:47
quelle
-1
%Vor%

Wenn Sie möchten, können Sie eine erste Überprüfung hinzufügen: if (mynumbers[0] != 1) { ... }

    
Lithy 17.09.2013 15:05
quelle

Tags und Links