Geben Sie bei einem unsortierten Array von Zahlen eine Funktion an, die true zurückgibt, wenn Array aus fortlaufenden Zahlen besteht.
Beispiele:
Wenn Array {5, 2, 3, 1, 4} ist, sollte die Funktion true zurückgeben, da das Array fortlaufende Zahlen von 1 bis 5 hat.
Wenn das Array {83, 78, 80, 81, 79, 82} ist, sollte die Funktion true zurückgeben, da das Array fortlaufende Zahlen von 78 bis 83 hat.
Wenn das Array {34, 23, 52, 12, 3} ist, sollte die Funktion false zurückgeben, weil die Elemente nicht aufeinander folgen.
Wenn das Array {7, 6, 5, 5, 3, 4} ist, sollte die Funktion false zurückgeben, weil 5 und 5 nicht aufeinander folgen.
Ich habe folgendes Algo gefunden:
finde das Maximum und Minimum des Arrays
max-min + 1 sollte die Größe eines Arrays haben
Suche nach Duplikaten
Suche nach allen fortlaufenden Nummern zwischen
Wie erreiche ich den 4. Pfad? (Die Komplexität sollte O(n) sein)
Andere Vorschläge sind sehr willkommen.
Wenn das Eingabearray A ist:
Finden Sie die minimalen und maximalen Werte von A, geben Sie False zurück, wenn das Array die falsche Größe hat.
Erstellen Sie ein neues Array, B, der gleichen Größe, anfangs mit allen Nullen
Geben Sie für jeden Index i B [A [i] - min] = 1 an.
Überprüfen Sie, ob B noch Nullen enthält.
Jeder Schritt benötigt O (n) Zeit.
Das sollte in Ordnung sein. visited [] zeigt an, wie oft eine Zahl aus dem ursprünglichen Array angezeigt wurde. Wenn eines seiner Elemente größer als zwei ist, gibt es ein Duplikat, also gib false zurück; Da die Größe beider Arrays max-min + 1 am Ende der Schleife ist, ist visit [] voll, weil wir alle Elemente von array [] besucht haben. Es ist also leer, es muss irgendwo ein Duplikat sein, aber wir müssen uns nicht darum kümmern, weil wir zu diesem Zeitpunkt immer noch falsch sind.
Es scheint mir, dass dies in O (n) Zeit mit O (1) zusätzlichem Raum geschehen kann.
Bestimmen Sie min und max des Arrays. Wenn (max - min + 1)! = N, gebe false zurück.
Ziehen Sie min von jedem Element im Array ab. Wir haben nun ein Array mit n Elementen aus dem Bereich [0, n]. Wir müssen jetzt nur nach Duplikaten suchen. Dies kann in linearer Zeit (jedes Element wird höchstens einmal verschoben) durch einen Code wie den folgenden erfolgen:
%Vor%Ich bin nicht gut in C, aber musst du Schritt 4 machen? Wenn 2 wahr ist und es keine Duplikate gibt, dann enthält es sicher die Sequenz, sonst nicht?
Wie von Ihnen gefragt, wird der vierte Schritt in Ihrem Algorithmus überhaupt nicht benötigt (da # 2 und # 3 garantieren, dass sie fortlaufend sind)
Wir können viele weitere Vergleiche (um die Zeitkomplexität zu verbessern) des Algorithmus speichern, indem wir alle Schritte in einem einzigen Durchlauf ausführen:
%Vor%Hier ist etwas, das für 1..N funktioniert, Sie können einfach die arithemtische Reihe forumulae verwenden, um sich darauf einzustellen [i, i + n]
%Vor%Finde min Element, Max Element und Summe der Elemente im Array.
Sie bilden eine Arthematische Progression und die Summe der Elemente ist: (no.Of element / 2) * (2 * minElement + (n-1) * difference)
Unterschied ist in diesem Fall 1
falls sum == (array.length / 2) * (2 * minElement + (array.length-1) * 1) & amp; & amp; maxElement == (minElement + (Länge von Array-1) * 1)
Dann sind die Zahlen aufeinander folgend.
Es gibt keine zusätzliche Platzkomplexität und die Zeitkomplexität ist O (n)
Danke @jpalecek für die Korrektur. Dies sollte jetzt in Ordnung sein