Einfache Interviewfragen wurden schwieriger: Bei den angegebenen Nummern 1..100 finden Sie die fehlenden Nummern, bei denen genau k fehlt

1146

Ich hatte vor einiger Zeit ein interessantes Vorstellungsgespräch. Die Frage begann ganz einfach:

Q1 : Wir haben eine Tasche mit Zahlen 1, 2, 3, ..., 100. Jede Zahl erscheint genau einmal, es gibt also 100 Zahlen. Jetzt wird eine Nummer zufällig aus der Tasche gezogen. Finde die fehlende Zahl.

Ich habe diese Interviewfrage natürlich schon einmal gehört, also habe ich sehr schnell geantwortet:

A1 : Nun, die Summe der Zahlen 1 + 2 + 3 + … + Nist (N+1)(N/2)(siehe Wikipedia: Summe der arithmetischen Reihen ). Denn N = 100die Summe ist 5050.

Wenn also alle Zahlen in der Tasche vorhanden sind, ist die Summe genau 5050. Da eine Zahl fehlt, ist die Summe geringer, und der Unterschied ist diese Zahl. So können wir diese fehlende Zahl in O(N)Zeit und O(1)Raum finden.

Zu diesem Zeitpunkt dachte ich, ich hätte es gut gemacht, aber plötzlich nahm die Frage eine unerwartete Wendung:

F2 : Das ist richtig, aber wie würden Sie das tun, wenn ZWEI Zahlen fehlen?

Ich hatte diese Variante noch nie gesehen / gehört / in Betracht gezogen, geriet in Panik und konnte die Frage nicht beantworten. Der Interviewer bestand darauf, meinen Denkprozess zu kennen, und ich erwähnte, dass wir vielleicht mehr Informationen erhalten können, indem wir ihn mit dem erwarteten Produkt vergleichen oder vielleicht einen zweiten Durchgang machen, nachdem wir einige Informationen aus dem ersten Durchgang usw. gesammelt haben, aber ich habe wirklich nur geschossen im Dunkeln, anstatt tatsächlich einen klaren Weg zur Lösung zu haben.

Der Interviewer hat versucht, mich zu ermutigen, indem er sagte, dass eine zweite Gleichung tatsächlich eine Möglichkeit ist, das Problem zu lösen. Zu diesem Zeitpunkt war ich etwas verärgert (weil ich die Antwort nicht vorher kannte) und fragte, ob dies eine allgemeine (sprich: "nützliche") Programmiertechnik ist oder ob es nur eine Trick / Gotcha-Antwort ist.

Die Antwort des Interviewers überraschte mich: Sie können die Technik verallgemeinern, um 3 fehlende Zahlen zu finden. Tatsächlich können Sie es verallgemeinern, um k fehlende Zahlen zu finden .

Qk : Wenn genau k Zahlen in der Tasche fehlen, wie würden Sie sie effizient finden?

Dies war vor ein paar Monaten und ich konnte immer noch nicht herausfinden, was diese Technik ist. Offensichtlich gibt es eine Ω(N)Zeituntergrenze, da wir alle Zahlen mindestens einmal scannen müssen, aber der Interviewer bestand darauf, dass die ZEIT- und RAUM- Komplexität der Lösungstechnik (abzüglich des O(N)Zeiteingabescans) in k und nicht in N definiert ist .

Die Frage hier ist also einfach:

  • Wie würden Sie Q2 lösen ?
  • Wie würden Sie Q3 lösen ?
  • Wie würden Sie Qk lösen ?

Klarstellungen

  • Im Allgemeinen gibt es N Zahlen von 1 .. N , nicht nur 1..100.
  • Ich bin nicht auf der Suche nach einer offensichtlichen satzbasierten Lösung, z. B. unter Verwendung eines Bit-Satzes , der das Vorhandensein / Fehlen jeder Zahl durch den Wert eines bestimmten Bits O(N)codiert und daher Bits in zusätzlichem Raum verwendet. Wir können uns keinen zusätzlichen Platz leisten, der proportional zu N ist .
  • Ich bin auch nicht auf der Suche nach dem offensichtlichen Sort-First-Ansatz. Dies und der satzbasierte Ansatz sind in einem Interview erwähnenswert (sie sind einfach zu implementieren und können je nach N sehr praktisch sein). Ich suche nach der Holy Grail-Lösung (die möglicherweise praktisch ist oder nicht, aber dennoch die gewünschten asymptotischen Eigenschaften aufweist).

Natürlich müssen Sie die Eingabe wieder einscannen O(N), aber Sie können nur eine kleine Menge an Informationen erfassen (definiert als k, nicht N ) und müssen dann die k fehlenden Zahlen irgendwie finden.

Polygenschmierstoffe
quelle
7
@polygenelubricants Vielen Dank für die Klarstellungen. "Ich suche nach einem Algorithmus, der O (N) Zeit und O (K) Raum verwendet, wobei K die Anzahl der fehlenden Zahlen ist" wäre von Anfang an klar gewesen ;-)
Dave O.
7
Sie sollten in der Aussage von Q1 genau angeben, dass Sie nicht in der richtigen Reihenfolge auf die Nummern zugreifen können. Dies scheint Ihnen wahrscheinlich offensichtlich zu sein, aber ich habe noch nie von der Frage gehört und der Begriff "Tasche" (was auch "Multiset" bedeutet) war irgendwie verwirrend.
Jérémie
7
Bitte lesen Sie Folgendes, da die hier gegebenen
18
Die Lösung zum Summieren der Zahlen erfordert log (N) Speicherplatz, es sei denn, Sie betrachten den Speicherplatzbedarf für eine unbegrenzte Ganzzahl als O (1). Wenn Sie jedoch unbegrenzte Ganzzahlen zulassen, haben Sie mit nur einer Ganzzahl so viel Speicherplatz, wie Sie möchten.
Udo Klein
3
Übrigens könnte eine ziemlich gute alternative Lösung für Q1 darin bestehen, XORalle Zahlen von 1bis zu nberechnen und dann das Ergebnis mit allen Zahlen im angegebenen Array zu xoring. Am Ende haben Sie Ihre fehlende Nummer. In dieser Lösung müssen Sie sich nicht wie beim Zusammenfassen um den Überlauf kümmern.
Sbeliakov

Antworten:

590

Hier ist eine Zusammenfassung des Links von Dimitris Andreou .

Denken Sie an die Summe der i-ten Potenzen, wobei i = 1,2, .., k. Dies reduziert das Problem auf die Lösung des Gleichungssystems

a 1 + a 2 + ... + a k = b 1

a 1 2 + a 2 2 + ... + a k 2 = b 2

...

a 1 k + a 2 k + ... + a k k = b k

Wenn Sie die Newtonschen Identitäten verwenden und b i kennen, können Sie rechnen

c 1 = a 1 + a 2 + ... a k

c 2 = a 1 a 2 + a 1 a 3 + ... + a k-1 a k

...

c k = a 1 a 2 ... a k

Wenn Sie das Polynom (xa 1 ) ... (xa k ) erweitern, sind die Koeffizienten genau c 1 , ..., c k - siehe Viètes Formeln . Da jeder Polynomfaktor eindeutig ist (der Polynomring ist eine euklidische Domäne ), bedeutet dies, dass ein i bis zur Permutation eindeutig bestimmt wird.

Dies beendet einen Beweis dafür, dass das Erinnern an Kräfte ausreicht, um die Zahlen wiederherzustellen. Für die Konstante k ist dies ein guter Ansatz.

Wenn jedoch k variiert, ist der direkte Ansatz der Berechnung von c 1 , ..., c k unerschwinglich teuer, da z. B. c k das Produkt aller fehlenden Zahlen ist, Größe n! / (Nk)!. Um dies zu überwinden, führen Sie Berechnungen im Feld Z q durch , wobei q eine Primzahl ist, so dass n <= q <2n - es existiert nach Bertrands Postulat . Der Beweis muss nicht geändert werden, da die Formeln immer noch gelten und die Faktorisierung von Polynomen immer noch einzigartig ist. Sie benötigen auch einen Algorithmus zur Faktorisierung über endliche Felder, zum Beispiel den von Berlekamp oder Cantor-Zassenhaus .

High-Level-Pseudocode für Konstante k:

  • Berechnen Sie die i-ten Potenzen gegebener Zahlen
  • Subtrahieren, um Summen der i-ten Potenzen unbekannter Zahlen zu erhalten. Nennen Sie die Summen b i .
  • Verwenden Sie Newtons Identitäten, um Koeffizienten aus b i zu berechnen . nenne sie c i . Grundsätzlich ist c 1 = b 1 ; c 2 = (c 1 b 1 - b 2 ) / 2; genaue Formeln finden Sie in Wikipedia
  • Faktor das Polynom x k - c 1 x k - 1 + ... + c k .
  • Die Wurzeln des Polynoms sind die benötigten Zahlen a 1 , ..., a k .

Finden Sie zum Variieren von k eine Primzahl n <= q <2n unter Verwendung von z. B. Miller-Rabin und führen Sie die Schritte mit allen Zahlen aus, die modulo q reduziert sind.

EDIT: In der vorherigen Version dieser Antwort wurde angegeben, dass anstelle von Z q , wobei q eine Primzahl ist, ein endliches Feld der Charakteristik 2 verwendet werden kann (q = 2 ^ (log n)). Dies ist nicht der Fall, da Newtons Formeln eine Division durch Zahlen bis k erfordern.

sdcvvc
quelle
6
Sie müssen kein Primfeld verwenden, sondern können es auch verwenden q = 2^(log n). (Wie haben Sie die Super- und Indizes gemacht
?!
49
+1 Das ist wirklich sehr, sehr klug. Gleichzeitig ist fraglich, ob sich die Mühe wirklich lohnt oder ob (Teile) dieser Lösung für ein ganz künstliches Problem auf andere Weise wiederverwendet werden können. Und selbst wenn dies ein Problem der realen Welt wäre, wird auf vielen Plattformen die trivialste O(N^2)Lösung diese Schönheit möglicherweise sogar für ein angemessen hohes Maß übertreffen N. Lässt mich darüber nachdenken: tinyurl.com/c8fwgw Trotzdem großartige Arbeit! Ich hätte nicht die Geduld gehabt, durch die ganze Mathematik zu kriechen :)
back2dos
167
Ich denke, das ist eine wundervolle Antwort. Ich denke, dies zeigt auch, wie schlecht eine Interviewfrage wäre, wenn die fehlenden Zahlen über eine hinausgehen würden. Sogar das erste ist eine Art Gotchya, aber es ist häufig genug, dass es im Grunde zeigt, dass "Sie ein Interview vorbereitet haben". Aber zu erwarten, dass ein CS-Major weiß, dass er über k = 1 hinausgeht (insbesondere "vor Ort" in einem Interview), ist ein bisschen albern.
CorsiKa
5
Dies führt effektiv eine Reed Solomon-Codierung am Eingang durch.
David Ehrmann
78
Ich wette, dass die Eingabe aller Zahlen in a hash setund das Durchlaufen der 1...NSuite mithilfe von Suchvorgängen, um festzustellen, ob Zahlen fehlen, die allgemeinste, im Durchschnitt am schnellsten in Bezug auf kVariationen, die debuggbarste, wartbarste und verständlichste Lösung wäre. Natürlich ist der mathematische Weg beeindruckend, aber irgendwo auf dem Weg muss man Ingenieur und kein Mathematiker sein. Besonders wenn es ums Geschäft geht.
v.oddou
243

Sie finden es, indem Sie die paar Seiten von Muthukrishnan - Data Stream Algorithms: Puzzle 1: Finding Missing Numbers lesen . Es zeigt genau die Verallgemeinerung, die Sie suchen . Wahrscheinlich hat Ihr Interviewer dies gelesen und warum er diese Fragen gestellt hat.

Wenn nun nur die Leute anfangen würden, die Antworten zu löschen, die von Muthukrishnans Behandlung subsumiert oder ersetzt werden, und diesen Text leichter zu finden machen würden. :) :)


Siehe auch die direkt verwandte Antwort von sdcvvc , die auch Pseudocode enthält (Hurra! Keine Notwendigkeit, diese kniffligen mathematischen Formulierungen zu lesen :)) (danke, großartige Arbeit!).

Dimitris Andreou
quelle
Oooh ... Das ist interessant. Ich muss zugeben, dass mich die Mathematik etwas verwirrt hat, aber ich habe sie nur überflogen. Könnte es offen lassen, um später mehr zu sehen. :) Und +1, um diesen Link besser auffindbar zu machen. ;-)
Chris
2
Der Google Books-Link funktioniert bei mir nicht. Hier eine bessere Version [PostScript File].
Heinrich Apfelmus
9
Beeindruckend. Ich habe nicht erwartet, dass dies positiv bewertet wird! Als ich das letzte Mal einen Verweis auf die Lösung (in diesem Fall Knuths) veröffentlicht habe, anstatt zu versuchen, sie selbst zu lösen, wurde sie tatsächlich herabgestuft: stackoverflow.com/questions/3060104/… Der Bibliothekar in mir freut sich, danke :)
Dimitris Andreou
@ Apfelmus, beachte, dass dies ein Entwurf ist. (Ich beschuldige Sie natürlich nicht, ich habe den Entwurf fast ein Jahr lang für die realen Dinge verwechselt, bevor ich das Buch gefunden habe). Übrigens, wenn der Link nicht funktioniert hat, können Sie zu books.google.com gehen und nach "Muthukrishnan-Datenstrom-Algorithmen" (ohne Anführungszeichen) suchen. Es ist das erste, das angezeigt wird.
Dimitris Andreou
2
Bitte lesen Sie die folgenden, da die hier gegebenen
174

Wir können Q2 lösen, indem wir sowohl die Zahlen selbst als auch die Quadrate der Zahlen summieren .

Wir können das Problem dann auf reduzieren

k1 + k2 = x
k1^2 + k2^2 = y

Wo xund ywie weit liegen die Summen unter den erwarteten Werten?

Das Ersetzen gibt uns:

(x-k2)^2 + k2^2 = y

Was wir dann lösen können, um unsere fehlenden Zahlen zu bestimmen.

Anon.
quelle
7
+1; Ich habe die Formel in Maple für ausgewählte Zahlen ausprobiert und sie funktioniert. Ich konnte mich immer noch nicht überzeugen, WARUM es funktioniert.
Polygenelubricants
4
@polygenelubricants: Wenn Sie die Richtigkeit beweisen möchten, würden Sie zuerst zeigen, dass es immer eine korrekte Lösung bietet (das heißt, es wird immer ein Zahlenpaar erzeugt, das beim Entfernen aus dem Satz den Rest des Satzes ergibt die beobachtete Summe und Quadratsumme). Von dort aus ist der Nachweis der Einzigartigkeit so einfach wie der Nachweis, dass nur ein solches Zahlenpaar erzeugt wird.
Anon.
5
Die Art der Gleichungen bedeutet, dass Sie aus dieser Gleichung zwei Werte von k2 erhalten. Aus der ersten Gleichung, die Sie zur Erzeugung von k1 verwenden, können Sie jedoch erkennen, dass diese beiden Werte von k2 bedeuten, dass k1 der andere Wert ist, sodass Sie zwei Lösungen haben, die umgekehrt die gleichen Zahlen sind. Wenn Sie vorübergehend deklariert hätten, dass k1> k2 ist, hätten Sie nur eine Lösung für die quadratische Gleichung und damit insgesamt eine Lösung. Und natürlich gibt es aufgrund der Art der Frage immer eine Antwort, damit sie immer funktioniert.
Chris
3
Für eine gegebene Summe k1 + k2 gibt es viele Paare. Wir können diese Paare als K1 = a + b und K2 = ab schreiben, wobei a = (K1 + k2 / 2). a ist für eine gegebene Summe eindeutig. Die Summe der Quadrate (a + b) ** 2 + (ab) ** 2 = 2 * (a 2 + b 2). Für eine gegebene Summe K1 + K2 ist der a 2 -Term fest und wir sehen, dass die Summe der Quadrate aufgrund des b 2 -Terms eindeutig ist . Daher sind die Werte x und y für ein Paar von ganzen Zahlen eindeutig.
Phkahler
8
Das ist fantastisch. @ user3281743 hier ist ein Beispiel. Die fehlenden Zahlen (k1 und k2) seien 4 und 6. Summe (1 -> 10) = 55 und Summe (1 ^ 2 -> 10 ^ 2) = 385. Nun sei x = 55 - (Summe (alle verbleibenden Zahlen) )) und y = 385 - (Summe (Quadrate aller verbleibenden Zahlen)) also x = 10 und y = 52. Ersetzen Sie wie gezeigt, was uns übrig lässt mit: (10 - k2) ^ 2 + k2 ^ 2 = 52, was Sie können Vereinfachen Sie zu: 2k ^ 2 - 20k + 48 = 0. Wenn Sie die quadratische Gleichung lösen, erhalten Sie 4 und 6 als Antwort.
AlexKoren
137

Wie @j_random_hacker hervorhob, ist dies dem Finden von Duplikaten in O (n) Zeit und O (1) Raum ziemlich ähnlich , und eine Anpassung meiner Antwort dort funktioniert auch hier.

Unter der Annahme, dass der "Beutel" durch ein 1-basiertes A[]Größenarray dargestellt wird N - k, können wir Qk O(N)zeitlich und zeitlich lösenO(k) räumlich .

Zuerst erweitern wir unser Array A[]um kElemente, sodass es jetzt die Größe hat N. Dies ist der O(k)zusätzliche Platz. Wir führen dann den folgenden Pseudocode-Algorithmus aus:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

Die erste Schleife initialisiert die kzusätzlichen Einträge mit dem ersten Eintrag im Array (dies ist nur ein praktischer Wert, von dem wir wissen, dass er bereits im Array vorhanden ist - nach diesem Schritt alle Einträge, die im anfänglichen Array der Größe fehltenN-k sind fehlt noch im erweiterten Array).

Die zweite Schleife permutiert das erweiterte Array, sodass sich xeiner dieser Einträge an der Position befindet , wenn das Element mindestens einmal vorhanden ist A[x].

Beachten Sie, dass es zwar eine verschachtelte Schleife hat, aber dennoch ausgeführt wird O(N) rechtzeitig ausgeführt wird - ein Swap findet nur statt, wenn es einen isolchen gibt A[i] != i, und jeder Swap setzt mindestens ein Element so, dass A[i] == i, wo dies vorher nicht wahr war. Dies bedeutet, dass die Gesamtzahl der Swaps (und damit die Gesamtzahl der Ausführungen des whileSchleifenkörpers) höchstens beträgt N-1.

Die dritte Schleife druckt die Indizes des Arrays i, die nicht vom Wert belegt sindi - dies bedeutet, idass sie fehlten.

caf
quelle
4
Ich frage mich, warum so wenige Leute diese Antwort abstimmen und sie sogar nicht als richtige Antwort markieren. Hier ist der Code in Python. Es läuft in O (n) Zeit und benötigt zusätzlichen Platz O (k). pastebin.com/9jZqnTzV
wall-e
3
@caf Dies ist ziemlich ähnlich wie das Setzen der Bits und das Zählen der Stellen, an denen das Bit 0 ist. Und ich denke, wenn Sie ein ganzzahliges Array erstellen, wird mehr Speicher belegt.
Fox
5
"Das Setzen der Bits und das Zählen der Stellen, an denen das Bit 0 ist" erfordert O (n) zusätzlichen Speicherplatz. Diese Lösung zeigt, wie O (k) zusätzlicher Speicherplatz verwendet wird.
Café
7
Funktioniert nicht mit Streams als Eingabe und ändert das Eingabearray (obwohl es mir sehr gefällt und die Idee fruchtbar ist).
Comco
3
@ v.oddou: Nein, es ist in Ordnung. Der Swap ändert sich A[i], was bedeutet, dass bei der nächsten Iteration nicht dieselben zwei Werte wie beim vorherigen verglichen werden. Das Neue A[i]ist das gleiche wie das der letzten Schleife A[A[i]], aber das Neue A[A[i]]ist ein neuer Wert. Probieren Sie es aus und sehen Sie.
Café
128

Ich habe einen 4-Jährigen gebeten, dieses Problem zu lösen. Er sortierte die Zahlen und zählte dann mit. Dies hat einen Platzbedarf von O (Küchenboden) und funktioniert genauso einfach, auch wenn viele Bälle fehlen.

Oberst Panik
quelle
20
;) dein 4 jähriger muss sich 5 nähern oder / und ist ein genie. Meine 4-jährige Tochter kann noch nicht einmal richtig bis 4 zählen. Um fair zu sein, sagen wir, sie hat die Existenz der "4" gerade erst endgültig integriert. sonst würde sie es bis jetzt immer überspringen. "1,2,3,5,6,7" war ihre übliche Zählsequenz. Ich bat sie, Bleistifte zusammenzufügen, und sie würde 1 + 2 = 3 schaffen, indem sie alles von Grund auf neu nummerierte. Ich mache mir eigentlich Sorgen ...: '(meh ..
v.oddou
einfacher und dennoch effektiver Ansatz.
PabTorre
6
O (Küchenboden) haha ​​- aber wäre das nicht O (n ^ 2)?
13
O (m²) ich denke :)
Viktor Mellgren
1
@phuclv: In der Antwort heißt es: "Dies hat einen Platzbedarf von O (Küchenboden)". Aber in jedem Fall ist dies ein Fall , wo das Sortieren kann dadurch erreicht werden , O (n) Zeit --- siehe diese Diskussion .
Anthony Labarre
36

Ich bin mir nicht sicher, ob es die effizienteste Lösung ist, aber ich würde alle Einträge durchlaufen und ein Bitset verwenden, um zu merken, welche Zahlen gesetzt sind, und dann auf 0 Bits testen.

Ich mag einfache Lösungen - und ich glaube sogar, dass es schneller sein könnte als die Berechnung der Summe oder der Summe der Quadrate usw.

Chris Lercher
quelle
11
Ich habe diese offensichtliche Antwort vorgeschlagen, aber das wollte der Interviewer nicht. Ich habe in der Frage ausdrücklich gesagt, dass dies nicht die Antwort ist, nach der ich suche. Eine andere offensichtliche Antwort: zuerst sortieren. Weder die O(N)Zählsortierung noch die O(N log N)Vergleichssortierung ist das, wonach ich suche, obwohl beide sehr einfache Lösungen sind.
Polygenelubricants
@polygenelubricants: Ich kann nicht finden, wo Sie das in Ihrer Frage gesagt haben. Wenn Sie das Bitset als Ergebnis betrachten, gibt es keinen zweiten Durchgang. Die Komplexität ist (wenn wir N als konstant betrachten, wie der Interviewer mit den Worten vorschlägt, dass die Komplexität "in k nicht N definiert" ist) O (1), und wenn Sie ein "saubereres" Ergebnis erstellen müssen, sind Sie Holen Sie sich O (k), das ist das Beste, was Sie bekommen können, weil Sie immer O (k) benötigen, um das saubere Ergebnis zu erzielen.
Chris Lercher
"Beachten Sie, dass ich nicht nach der offensichtlichen
satzbasierten
9
@hmt: Ja, die Frage wurde vor ein paar Minuten bearbeitet. Ich gebe nur die Antwort, die ich von einem Befragten erwarten würde ... Die künstliche Konstruktion einer suboptimalen Lösung (Sie können die Zeit O (n) + O (k) nicht schlagen, egal was Sie tun) funktioniert nicht. Das ergibt für mich keinen Sinn - es sei denn, Sie können sich keinen zusätzlichen Platz für O (n) leisten, aber die Frage dazu ist nicht explizit.
Chris Lercher
3
Ich habe die Frage erneut bearbeitet, um sie weiter zu klären. Ich freue mich über das Feedback / die Antwort.
Polygenelubricants
33

Ich habe die Mathematik nicht überprüft, aber ich vermute, dass das Rechnen Σ(n^2)im selben Durchgang, den wir berechnen Σ(n), genügend Informationen liefert, um zwei fehlende Zahlen zu erhalten. Tun Sie dies Σ(n^3)auch, wenn drei vorhanden sind, und so weiter.

AakashM
quelle
15

Das Problem bei Lösungen, die auf Zahlen basieren, besteht darin, dass sie die Kosten für das Speichern und Arbeiten mit Zahlen mit großen Exponenten nicht berücksichtigen. In der Praxis würde eine Bibliothek mit großen Zahlen verwendet, damit sie für sehr große n funktioniert . Wir können die Raumnutzung für diese Algorithmen analysieren.

Wir können die zeitliche und räumliche Komplexität der Algorithmen von sdcvvc und Dimitris Andreou analysieren.

Lager:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Damit l_j \in \Theta(j log n)

Insgesamt genutzter Speicher: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Verwendeter Speicherplatz: Unter der Annahme, dass das Rechnen Zeit a^jbraucht ceil(log_2 j), Gesamtzeit:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Gesamtdauer: \Theta(kn log n)

Wenn diese Zeit und dieser Raum zufriedenstellend sind, können Sie einen einfachen rekursiven Algorithmus verwenden. Sei b! I der i-te Eintrag in der Tasche, n die Anzahl der Nummern vor dem Umzug und k die Anzahl der Umzüge. In der Haskell-Syntax ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Verwendeter Speicher: O(k)für Liste, O(log(n))für Stapel: O(k + log(n)) Dieser Algorithmus ist intuitiver, hat dieselbe zeitliche Komplexität und benötigt weniger Speicherplatz.

a1kmm
quelle
1
+1, sieht gut aus, aber du hast mich verloren, als ich in Snippet 1 von Zeile 4 zu Zeile 5 gegangen bin - kannst du das weiter erklären? Vielen Dank!
j_random_hacker
isInRangeist O (log n) , nicht O (1) : Es vergleicht Zahlen im Bereich 1..n, also muss es O (log n) Bits vergleichen. Ich weiß nicht, inwieweit sich dieser Fehler auf den Rest der Analyse auswirkt.
Jcsahnwaldt sagt GoFundMonica
14

Warte eine Minute. Wie die Frage schon sagt, befinden sich 100 Nummern in der Tasche. Egal wie groß k ist, das Problem kann in konstanter Zeit gelöst werden, da Sie eine Menge verwenden und Zahlen in höchstens 100-k-Iterationen einer Schleife aus der Menge entfernen können. 100 ist konstant. Der Satz der verbleibenden Zahlen ist Ihre Antwort.

Wenn wir die Lösung auf die Zahlen von 1 bis N verallgemeinern, ändert sich nichts, außer dass N keine Konstante ist, also sind wir in der Zeit O (N - k) = O (N). Wenn wir zum Beispiel einen Bit-Satz verwenden, setzen wir die Bits in O (N) -Zeit auf 1, durchlaufen die Zahlen, setzen die Bits im Laufe der Zeit auf 0 (O (Nk) = O (N)) und dann wir habe die Antwort.

Es scheint mir, dass der Interviewer Sie gefragt hat, wie Sie den Inhalt des endgültigen Satzes in O (k) -Zeit und nicht in O (N) -Zeit ausdrucken sollen . Wenn ein Bit gesetzt ist, müssen Sie natürlich alle N Bits durchlaufen, um zu bestimmen, ob Sie die Nummer drucken sollen oder nicht. Wenn Sie jedoch die Art und Weise ändern, in der das Set implementiert ist, können Sie die Zahlen in k Iterationen ausdrucken. Dazu werden die Zahlen in ein Objekt eingefügt, das sowohl in einem Hash-Set als auch in einer doppelt verknüpften Liste gespeichert werden soll. Wenn Sie ein Objekt aus dem Hash-Set entfernen, entfernen Sie es auch aus der Liste. Die Antworten bleiben in der Liste, die jetzt die Länge k hat.

JeremyP
quelle
9
Diese Antwort ist zu einfach und wir alle wissen, dass einfache Antworten nicht funktionieren! ;) Im Ernst, die ursprüngliche Frage sollte wahrscheinlich den Platzbedarf von O (k) betonen.
DK.
Das Problem ist nicht, dass dies einfach ist, sondern dass Sie O (n) zusätzlichen Speicher für die Karte verwenden müssen. Das Problem hat mich in konstanter Zeit und in ständigem Gedächtnis gelöst
Mojo Risin
3
Ich wette, Sie können beweisen, dass die minimale Lösung mindestens O (N) ist. denn weniger würde bedeuten, dass Sie nicht einmal einige Nummern angeschaut haben, und da keine Reihenfolge angegeben ist, ist es obligatorisch, ALLE Nummern zu betrachten.
v.oddou
Wenn wir die Eingabe als Stream betrachten und n zu groß ist, um im Speicher zu bleiben, ist die O (k) -Speicheranforderung sinnvoll. Wir können trotzdem Hashing verwenden: Machen Sie einfach k ^ 2 Buckets und verwenden Sie den einfachen Summenalgorithmus für jeden von ihnen. Das ist nur k ^ 2 Speicher und ein paar weitere Buckets können verwendet werden, um eine hohe Erfolgswahrscheinlichkeit zu erzielen.
Thomas Ahle
8

Um die Frage nach 2 (und 3) fehlenden Zahlen zu lösen, können Sie Änderungen vornehmen quickselect, die im Durchschnitt ausgeführt werden O(n)und konstanten Speicher verwenden, wenn die Partitionierung direkt erfolgt.

  1. Partitionieren Sie die Menge in Bezug auf einen zufälligen Pivot pin Partitionen l, die Zahlen enthalten, die kleiner als der Pivot sind, und rdie Zahlen enthalten, die größer als der Pivot sind.

  2. Bestimmen Sie, in welchen Partitionen sich die 2 fehlenden Zahlen befinden, indem Sie den Pivot-Wert mit der Größe jeder Partition ( p - 1 - count(l) = count of missing numbers in lund n - count(r) - p = count of missing numbers in r) vergleichen.

  3. a) Wenn jeder Partition eine Nummer fehlt, verwenden Sie den Summenunterschiedsansatz, um jede fehlende Nummer zu finden.

    (1 + 2 + ... + (p-1)) - sum(l) = missing #1 und ((p+1) + (p+2) ... + n) - sum(r) = missing #2

    b) Wenn einer Partition beide Nummern fehlen und die Partition leer ist, sind die fehlenden Nummern entweder (p-1,p-2)oder (p+1,p+2) abhängig davon, auf welcher Partition die Nummern fehlen.

    Wenn einer Partition 2 Zahlen fehlen, diese aber nicht leer ist, kehren Sie zu dieser Partition zurück.

Mit nur 2 fehlenden Zahlen verwirft dieser Algorithmus immer mindestens eine Partition, sodass er erhalten bleibt O(n) durchschnittliche Zeitkomplexität der Schnellauswahl erhalten bleibt. In ähnlicher Weise verwirft dieser Algorithmus bei 3 fehlenden Nummern bei jedem Durchgang mindestens eine Partition (da wie bei 2 fehlenden Nummern höchstens 1 Partition mehrere fehlende Nummern enthält). Ich bin mir jedoch nicht sicher, um wie viel die Leistung abnimmt, wenn weitere fehlende Zahlen hinzugefügt werden.

Hier ist eine Implementierung, die keine direkte Partitionierung verwendet, sodass dieses Beispiel den Platzbedarf nicht erfüllt, aber die Schritte des Algorithmus veranschaulicht:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Demo

FuzzyTree
quelle
Das Partitionieren der Menge entspricht der Verwendung des linearen Raums. Zumindest würde es in einer Streaming-Einstellung nicht funktionieren.
Thomas Ahle
@ThomasAhle siehe en.wikipedia.org/wiki/Selection_algorithm#Space_complexity . Das Partitionieren des Sets erfordert nur O (1) zusätzlichen Raum - keinen linearen Raum. In einer Streaming-Einstellung wäre es O (k) zusätzlicher Speicherplatz, die ursprüngliche Frage erwähnt jedoch kein Streaming.
FuzzyTree
Nicht direkt, aber er schreibt "Sie müssen die Eingabe in O (N) scannen, aber Sie können nur eine kleine Menge an Informationen erfassen (definiert als k nicht N)", was normalerweise die Definition von Streaming ist. Das Verschieben aller Zahlen für die Partitionierung ist nur möglich, wenn Sie ein Array der Größe N haben. Es ist nur so, dass die Frage viele Antworten enthält, die diese Einschränkung zu ignorieren scheinen.
Thomas Ahle
1
Aber wie Sie sagen, kann die Leistung abnehmen, wenn mehr Zahlen hinzugefügt werden? Wir können auch den linearen Zeitmedian-Algorithmus verwenden, um immer einen perfekten Schnitt zu erhalten. Wenn die k-Zahlen jedoch in 1, ..., n gut verteilt sind, müssen Sie die Logk-Ebenen nicht "tief" ausführen, bevor Sie sie beschneiden können irgendwelche Zweige?
Thomas Ahle
2
Die Laufzeit im ungünstigsten Fall ist in der Tat nlogk, da Sie die gesamte Eingabe zu den meisten logk-Zeiten verarbeiten müssen. Dann handelt es sich um eine geometrische Sequenz (eine, die mit höchstens n Elementen beginnt). Die Platzanforderungen werden bei Implementierung mit einfacher Rekursion erkannt, können jedoch durch Ausführen einer tatsächlichen Schnellauswahl und Sicherstellen der korrekten Länge jeder Partition zu O (1) gemacht werden.
Emu
7

Hier ist eine Lösung, die k Bit zusätzlichen Speicherplatzes verwendet, ohne clevere Tricks und einfach. Ausführungszeit O (n), zusätzlicher Raum O (k). Nur um zu beweisen, dass dies gelöst werden kann, ohne zuerst die Lösung zu lesen oder ein Genie zu sein:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}
gnasher729
quelle
Wollen Sie (data [n - 1 - odd] % 2 == 1) ++odd;?
Charles
2
Können Sie erklären, wie das funktioniert? Ich verstehe nicht
Teepeemm
Die Lösung wäre sehr, sehr einfach, wenn ich ein Array von (n + k) Booleschen Werten für die temporäre Speicherung verwenden könnte, aber das ist nicht zulässig. Also ordne ich die Daten neu, indem ich die geraden Zahlen am Anfang und die ungeraden Zahlen am Ende des Arrays setze. Jetzt können die niedrigsten Bits dieser n Zahlen für die temporäre Speicherung verwendet werden, da ich weiß, wie viele gerade und ungerade Zahlen es gibt, und die niedrigsten Bits rekonstruieren kann! Diese n Bits und die k zusätzlichen Bits sind genau die (n + k) Booleschen Werte, die ich benötigt habe.
Gnasher729
2
Dies würde nicht funktionieren, wenn die Daten zu groß wären, um im Speicher zu bleiben, und Sie sie nur als Stream sehen würden. Köstlich hackig :)
Thomas Ahle
Die Raumkomplexität kann O (1) sein. In einem ersten Durchgang verarbeiten Sie alle Zahlen <(n - k) mit genau diesem Algorithmus, ohne 'extra' zu verwenden. In einem zweiten Durchgang löschen Sie die Paritätsbits erneut und verwenden die ersten k Positionen zum Indizieren von Zahlen (nk) .. (n).
Emu
5

Können Sie überprüfen, ob jede Nummer vorhanden ist? Wenn ja, können Sie dies versuchen:

S = Summe aller Zahlen im Beutel (S <5050)
Z = Summe der fehlenden Zahlen 5050 - S.

wenn die fehlenden Zahlen sind xund ydann:

x = Z - y und
max (x) = Z - 1

Sie überprüfen also den Bereich von 1bis max(x)und finden die Nummer

Ilian Iliev
quelle
1
Was max(x)bedeutet, wann xist eine Zahl?
Thomas Ahle
2
er meint wahrscheinlich max aus dem Satz von Zahlen
JavaHopper
Wenn wir mehr als 2 Zahlen haben, würde diese Lösung
kaputt gehen
4

Möglicherweise kann dieser Algorithmus für Frage 1 funktionieren:

  1. Berechne xor der ersten 100 ganzen Zahlen vor (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
  2. xoder die Elemente, wie sie immer wieder aus dem Eingabestream kommen (val1 = val1 ^ next_input)
  3. endgültige Antwort = val ^ val1

Oder noch besser:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

Dieser Algorithmus kann tatsächlich für zwei fehlende Zahlen erweitert werden. Der erste Schritt bleibt gleich. Wenn wir GetValue mit zwei fehlenden Nummern aufrufen, sind die beiden fehlenden Nummern das Ergebnis a1^a2. Sagen wir

val = a1^a2

Um nun a1 und a2 aus val herauszusieben, nehmen wir ein beliebiges gesetztes Bit in val. Nehmen wir an, das ithBit ist in val gesetzt. Das bedeutet, dass a1 und a2 an der ithBitposition unterschiedliche Paritäten haben . Jetzt führen wir eine weitere Iteration des ursprünglichen Arrays durch und behalten zwei xor-Werte bei. Eine für die Zahlen, bei denen das i-te Bit gesetzt ist, und eine andere, bei der das i-te Bit nicht gesetzt ist. Wir haben jetzt zwei Eimer mit Zahlen, und es wird garantiert, dass a1 and a2sie in verschiedenen Eimern liegen. Wiederholen Sie nun dasselbe, was wir getan haben, um auf jedem Eimer ein fehlendes Element zu finden.

bashrc
quelle
Dies löst nur das Problem für k=1, oder? Aber ich benutze gerne xorüber Summen, es scheint ein bisschen schneller zu sein.
Thomas Ahle
@ ThomasAhle Ja. Ich habe das in meiner Antwort hervorgehoben.
Bashrc
Recht. Haben Sie eine Idee, was ein xor "zweiter Ordnung" für k = 2 sein könnte? Könnten wir ähnlich wie bei der Verwendung von Quadraten für die Summe für xor "quadrieren"?
Thomas Ahle
1
@ThomasAhle Es wurde geändert, um für 2 fehlende Zahlen zu funktionieren.
Bashrc
Das ist mein Lieblingsweg :)
Robert King
3

Sie können Q2 lösen, wenn Sie die Summe beider Listen und das Produkt beider Listen haben.

(l1 ist das Original, l2 ist die geänderte Liste)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Wir können dies optimieren, da die Summe einer arithmetischen Reihe das n-fache des Durchschnitts des ersten und letzten Terms beträgt:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Jetzt wissen wir das (wenn a und b die entfernten Zahlen sind):

a + b = d
a * b = m

So können wir neu anordnen zu:

a = s - b
b * (s - b) = m

Und multiplizieren:

-b^2 + s*b = m

Und ordnen Sie neu an, so dass die rechte Seite Null ist:

-b^2 + s*b - m = 0

Dann können wir mit der quadratischen Formel lösen:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Beispiel für Python 3-Code:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Ich kenne die Komplexität der Funktionen sqrt, redu und sum nicht, daher kann ich die Komplexität dieser Lösung nicht herausfinden (wenn jemand etwas weiß, kommentieren Sie dies bitte unten.)

Tuomas Laakkonen
quelle
Wie viel Zeit und Speicher benötigt es zur Berechnung x1*x2*x3*...?
Thomas Ahle
@ThomasAhle Es ist O (n) -Zeit und O (1) -Raum auf der Länge der Liste, aber in Wirklichkeit ist es eher so, als Multiplikation (zumindest in Python) ist O (n ^ 1.6) -Zeit auf der Länge von Die Zahl und die Zahlen sind O (log n) -Raum auf ihrer Länge.
Tuomas Laakkonen
@ThomasAhle Nein, log (a ^ n) = n * log (a), damit Sie O (l log k) -Leerraum zum Speichern der Nummer haben. Bei einer Liste der Länge l und der ursprünglichen Anzahl der Länge k hätten Sie also einen O (l) -Raum, aber der konstante Faktor (log k) wäre niedriger als nur das Ausschreiben aller. (Ich denke nicht, dass meine Methode eine besonders gute Möglichkeit ist, die Frage zu beantworten.)
Tuomas Laakkonen
3

Für Q2 ist dies eine Lösung, die etwas ineffizienter als die anderen ist, aber dennoch eine O (N) -Laufzeit hat und O (k) Speicherplatz beansprucht.

Die Idee ist, den ursprünglichen Algorithmus zweimal auszuführen. In der ersten erhalten Sie eine fehlende Gesamtzahl, wodurch Sie eine Obergrenze der fehlenden Zahlen erhalten. Rufen wir diese Nummer an N. Sie wissen, dass sich die fehlenden zwei Zahlen summieren werden N, sodass die erste Zahl nur in dem Intervall liegen kann, [1, floor((N-1)/2)]während die zweite in sein wird [floor(N/2)+1,N-1].

Auf diese Weise durchlaufen Sie erneut alle Zahlen und verwerfen alle Zahlen, die nicht im ersten Intervall enthalten sind. Diejenigen, die sind, behalten Sie ihre Summe im Auge. Schließlich kennen Sie eine der beiden fehlenden Zahlen und im weiteren Sinne die zweite.

Ich habe das Gefühl, dass diese Methode verallgemeinert werden könnte und möglicherweise mehrere Suchvorgänge während eines einzelnen Durchlaufs über die Eingabe "parallel" ausgeführt werden, aber ich habe noch nicht herausgefunden, wie.

Svalorzen
quelle
Ahaha, ja, das ist die gleiche Lösung, die ich mir für das zweite Quartal ausgedacht habe, nur um die Summe erneut zu berechnen und die Negative für alle Zahlen unter N / 2 zu nehmen, aber das ist noch besser!
xjcl
2

Ich denke, dies kann ohne komplexe mathematische Gleichungen und Theorien geschehen. Nachfolgend finden Sie einen Vorschlag für eine vorhandene und O (2n) -Zeitkomplexitätslösung:

Annahmen zum Eingabeformular:

Anzahl der Zahlen im Beutel = n

Anzahl fehlender Zahlen = k

Die Zahlen in der Tasche werden durch ein Array der Länge n dargestellt

Länge des Eingabearrays für das Algo = n

Fehlende Einträge im Array (Zahlen aus der Tasche) werden durch den Wert des ersten Elements im Array ersetzt.

Z.B. Anfangs sieht die Tasche aus wie [2,9,3,7,8,6,4,5,1,10]. Wenn 4 herausgenommen wird, wird der Wert 4 zu 2 (dem ersten Element des Arrays). Daher sieht die Tasche nach dem Herausnehmen von 4 wie folgt aus: [2,9,3,7,8,6,2,5,1,10]

Der Schlüssel zu dieser Lösung besteht darin, den INDEX einer besuchten Nummer zu markieren, indem der Wert an diesem INDEX beim Durchlaufen des Arrays negiert wird.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }
Pickhunter
quelle
Dies verbraucht zu viel Speicher.
Thomas Ahle
2

Es gibt eine allgemeine Möglichkeit, solche Streaming-Algorithmen zu verallgemeinern. Die Idee ist, ein bisschen Randomisierung zu verwenden, um die kElemente hoffentlich in unabhängige Unterprobleme zu "verteilen" , wobei unser ursprünglicher Algorithmus das Problem für uns löst. Diese Technik wird unter anderem bei der Rekonstruktion spärlicher Signale eingesetzt.

  • Machen Sie ein Array avon Größe u = k^2.
  • Wählen Sie eine beliebige Universal-Hash - Funktion , h : {1,...,n} -> {1,...,u}. (Wie Multiplikationsverschiebung )
  • Für jeden iin 1, ..., nErhöhunga[h(i)] += i
  • xDekrementieren Sie für jede Zahl im Eingabestream a[h(x)] -= x.

Wenn alle fehlenden Zahlen in verschiedene Buckets gehasht wurden, enthalten die Nicht-Null-Elemente des Arrays jetzt die fehlenden Zahlen.

Die Wahrscheinlichkeit, dass ein bestimmtes Paar an denselben Bucket gesendet wird, ist geringer als 1/uper Definition einer universellen Hash-Funktion. Da es ungefähr k^2/2Paare gibt, haben wir, dass die Fehlerwahrscheinlichkeit höchstens ist k^2/2/u=1/2. Das heißt, wir schaffen es mit einer Wahrscheinlichkeit von mindestens 50% und wenn wir zunehmenu uns erhöhen, wir unsere Chancen.

Beachten Sie, dass dieser Algorithmus Platz beansprucht k^2 logn(wir benötigen lognBits pro Array-Bucket). Dies entspricht dem Platz, der in der Antwort von @Dimitris Andreou benötigt wird (insbesondere dem Platzbedarf der Polynomfaktorisierung, der zufällig ebenfalls randomisiert wird.) Dieser Algorithmus hat ebenfalls eine Konstante Zeit pro Update, statt Zeit kbei Leistungssummen.

Tatsächlich können wir mit dem in den Kommentaren beschriebenen Trick sogar effizienter als die Leistungssummenmethode sein.

Thomas Ahle
quelle
Hinweis: Wir können auch xorin jedem Eimer verwenden, anstatt sum, wenn dies auf unserer Maschine schneller ist.
Thomas Ahle
Interessant, aber ich denke, dies respektiert nur die Platzbeschränkung, wenn k <= sqrt(n)- zumindest wenn u=k^2? Angenommen, k = 11 und n = 100, dann hätten Sie 121 Buckets und der Algorithmus würde einem Array von 100 Bits ähneln, das Sie abhaken, wenn Sie jedes # aus dem Stream lesen. Das Erhöhen uverbessert die Erfolgschancen, aber es gibt eine Grenze, um wie viel Sie es erhöhen können, bevor Sie die Platzbeschränkung überschreiten.
FuzzyTree
1
Das Problem ist am sinnvollsten für nviel größer als k, denke ich, aber Sie können tatsächlich k lognmit einer Methode, die dem beschriebenen Hashing sehr ähnlich ist, Platz sparen, während Sie immer noch konstante Zeitaktualisierungen haben. Es wird in gnunet.org/eppstein-set-reconciliation beschrieben , wie die Methode der Summe der Potenzen, aber im Grunde hasht man 'zwei von k' Buckets mit einer starken Hash-Funktion wie Tabellierungs-Hashing, was garantiert, dass einige Buckets nur ein Element haben . Um zu dekodieren, identifizieren Sie diesen Bucket und entfernen das Element aus beiden Buckets, wodurch (wahrscheinlich) ein weiterer Bucket usw.
Thomas Ahle
2

Eine sehr einfache Lösung für das zweite Quartal, von der ich überrascht bin, dass noch niemand geantwortet hat. Verwenden Sie die Methode aus Q1, um die Summe der beiden fehlenden Zahlen zu ermitteln. Bezeichnen wir es mit S, dann ist eine der fehlenden Zahlen kleiner als S / 2 und die andere größer als S / 2 (duh). Summieren Sie alle Zahlen von 1 bis S / 2 und vergleichen Sie sie mit dem Ergebnis der Formel (ähnlich der Methode in Q1), um die niedrigere Zahl zwischen den fehlenden Zahlen zu ermitteln. Subtrahieren Sie es von S, um die größere fehlende Zahl zu finden.

Gilad Deutsch
quelle
Ich denke, das ist die gleiche Antwort wie Svalorzen , aber Sie haben es mit besseren Worten erklärt. Haben Sie eine Idee, wie Sie es auf Qk verallgemeinern können?
John McClane
Entschuldigung, dass Sie die andere Antwort verpasst haben. Ich bin nicht sicher, ob es möglich ist, es auf $ Q_k $ zu verallgemeinern, da Sie in diesem Fall das kleinste fehlende Element nicht an einen Bereich binden können. Sie wissen, dass ein Element kleiner als $ S / k $ sein muss, aber das kann für mehrere Elemente zutreffen
Gilad Deutsch
1

Sehr schönes Problem. Ich würde einen festgelegten Unterschied für Qk verwenden. Viele Programmiersprachen unterstützen dies sogar, wie in Ruby:

missing = (1..100).to_a - bag

Es ist wahrscheinlich nicht die effizienteste Lösung, aber es ist eine, die ich im wirklichen Leben verwenden würde, wenn ich in diesem Fall vor einer solchen Aufgabe stünde (bekannte Grenzen, niedrige Grenzen). Wenn die Anzahl sehr groß wäre, würde ich natürlich einen effizienteren Algorithmus in Betracht ziehen, aber bis dahin würde mir die einfache Lösung ausreichen.

DarkDust
quelle
1
Dies verbraucht zu viel Platz.
Thomas Ahle
@ThomasAhle: Warum fügst du jeder zweiten Antwort nutzlose Kommentare hinzu? Was meinst du damit, dass es zu viel Platz beansprucht?
DarkDust
Denn die Frage lautet: "Wir können uns keinen zusätzlichen Platz leisten, der proportional zu N ist." Diese Lösung macht genau das.
Thomas Ahle
1

Sie können versuchen, einen Bloom-Filter zu verwenden . Fügen Sie jede Zahl in den Beutel in die Blüte ein und durchlaufen Sie dann den gesamten 1-k-Satz, bis jede nicht gefundene gemeldet wird. Dies findet möglicherweise nicht in allen Szenarien die Antwort, ist jedoch möglicherweise eine ausreichend gute Lösung.

jdizzle
quelle
Es gibt auch den Zählblütenfilter, der das Löschen ermöglicht. Dann können Sie einfach alle Zahlen hinzufügen und die im Stream angezeigten löschen.
Thomas Ahle
Haha, das ist wahrscheinlich eine der praktischeren Antworten, bekommt aber wenig Aufmerksamkeit.
Hund
1

Ich würde diese Frage anders angehen und den Interviewer auf weitere Details zu dem größeren Problem untersuchen, das er zu lösen versucht. Abhängig vom Problem und den damit verbundenen Anforderungen ist die offensichtliche satzbasierte Lösung möglicherweise das Richtige und der Ansatz, eine Liste zu erstellen und anschließend durchzusuchen, möglicherweise nicht.

Zum Beispiel könnte es sein, dass der Interviewer nNachrichten versendet und wissen muss k, was nicht zu einer Antwort geführt hat, und dass er es in möglichst kurzer Wanduhrzeit nach dem wissen muss . Danach enthält das Set die Liste der fehlenden Elemente und es ist keine zusätzliche Verarbeitung erforderlich.n-k Eingang der Antwort . Nehmen wir auch an, dass der Nachrichtenkanal so beschaffen ist, dass selbst bei voller Auslastung genügend Zeit für die Verarbeitung zwischen Nachrichten bleibt, ohne dass sich dies darauf auswirkt, wie lange es dauert, bis das Endergebnis nach dem Eintreffen der letzten Antwort erstellt wird. Diese Zeit kann genutzt werden, um eine identifizierende Facette jeder gesendeten Nachricht in einen Satz einzufügen und sie zu löschen, wenn jede entsprechende Antwort eintrifft. Sobald die letzte Antwort eingetroffen ist, müssen Sie nur noch die Kennung aus dem Satz entfernen, was in typischen Implementierungen erforderlich istO(log k+1)k

Dies ist sicherlich nicht der schnellste Ansatz für die Stapelverarbeitung vorgenerierter Zahlenbeutel, da das Ganze läuft O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Es funktioniert jedoch für jeden Wert von k(auch wenn es nicht im Voraus bekannt ist) und wurde im obigen Beispiel so angewendet, dass das kritischste Intervall minimiert wird.

Blrfl
quelle
Würde dies funktionieren, wenn Sie nur O (k ^ 2) zusätzlichen Speicher hätten?
Thomas Ahle
1

Sie können die Lösung motivieren, indem Sie sie in Form von Symmetrien (Gruppen, in mathematischer Sprache) betrachten. Unabhängig von der Reihenfolge der Zahlen sollte die Antwort dieselbe sein. Wenn Sie kFunktionen verwenden möchten, um die fehlenden Elemente zu ermitteln, sollten Sie sich überlegen, welche Funktionen diese Eigenschaft haben: symmetrisch. Die Funktion s_1(x) = x_1 + x_2 + ... + x_nist ein Beispiel für eine symmetrische Funktion, aber es gibt andere von höherem Grad. Berücksichtigen Sie insbesondere die elementaren symmetrischen Funktionen . Die elementare symmetrische Funktion des Grades 2 ist s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_ndie Summe aller Produkte zweier Elemente. Ähnliches gilt für die elementaren symmetrischen Funktionen des Grades 3 und höher. Sie sind offensichtlich symmetrisch. Darüber hinaus stellt sich heraus, dass sie die Bausteine ​​für alle symmetrischen Funktionen sind.

Sie können die elementaren symmetrischen Funktionen erstellen, indem Sie dies beachten s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Weitere Überlegungen sollten Sie davon überzeugen s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))und so weiter, damit sie in einem Durchgang berechnet werden können.

Wie können wir feststellen, welche Elemente im Array fehlten? Denken Sie an das Polynom (z-x_1)(z-x_2)...(z-x_n). Es wird ausgewertet, 0ob Sie eine der Zahlen eingeben x_i. Wenn Sie das Polynom erweitern, erhalten Sie z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Die elementaren symmetrischen Funktionen erscheinen auch hier, was wirklich keine Überraschung ist, da das Polynom gleich bleiben sollte, wenn wir eine Permutation auf die Wurzeln anwenden.

Wir können also das Polynom bauen und versuchen, es zu faktorisieren, um herauszufinden, welche Zahlen nicht in der Menge enthalten sind, wie andere erwähnt haben.

Wenn wir uns schließlich Gedanken über ein Überlaufen des Speichers mit großen Zahlen machen (das n-te symmetrische Polynom liegt in der Größenordnung 100!), können wir diese Berechnungen durchführen, mod pwenn peine Primzahl größer als 100 ist. In diesem Fall bewerten wir das Polynom mod pund stellen fest, dass es erneut ausgewertet wird bis, 0wenn die Eingabe eine Zahl in der Menge ist, und es wird ein Wert ungleich Null ausgewertet, wenn die Eingabe eine Zahl ist, die nicht in der Menge enthalten ist. Wie andere bereits betont haben , müssen wir das Polynom faktorisieren, um die Werte aus dem Polynom in einer Zeit herauszuholen, die davon abhängt k, und nicht davon .Nmod p

Edward Doolittle
quelle
1

Ein weiterer Weg ist die Verwendung der Restgraphenfilterung.

Angenommen, wir haben die Nummern 1 bis 4 und 3 fehlt. Die binäre Darstellung ist die folgende:

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

Und ich kann ein Flussdiagramm wie das folgende erstellen.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

Beachten Sie, dass das Flussdiagramm x Knoten enthält, während x die Anzahl der Bits ist. Und die maximale Anzahl von Kanten beträgt (2 * x) -2.

Für eine 32-Bit-Ganzzahl wird also O (32) oder O (1) benötigt.

Wenn ich nun die Kapazität für jede Zahl ab 1,2,4 entferne, bleibt ein Restdiagramm übrig.

0 ----------> 1 ---------> 1

Zum Schluss werde ich eine Schleife wie die folgende ausführen:

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Jetzt enthält das Ergebnis resultZahlen, die ebenfalls nicht fehlen (falsch positiv). Aber das k <= (Größe des Ergebnisses) <= n, wenn kElemente fehlen.

Ich werde die angegebene Liste ein letztes Mal durchgehen, um zu markieren, ob das Ergebnis fehlt oder nicht.

Die zeitliche Komplexität ist also O (n).

Schließlich ist es möglich , die Anzahl der falsch positiven (und den Raum erforderlich) , indem Knoten zu reduzieren 00, 01, 11, 10statt nur 0und 1.

Shuva
quelle
Ich verstehe Ihr Diagramm nicht. Was bedeuten die Knoten, Kanten und Zahlen? Warum sind einige Kanten gerichtet und andere nicht?
Dain
Tatsächlich verstehe ich Ihre Antwort überhaupt nicht wirklich. Können Sie noch etwas klarstellen?
Dain
1

Sie müssten wahrscheinlich klären, was O (k) bedeutet.

Hier ist eine triviale Lösung für beliebiges k: Akkumulieren Sie für jedes v in Ihrer Zahlenmenge die Summe von 2 ^ v. Am Ende Schleife i von 1 nach N. Wenn die Summe bitweise UND mit 2 ^ i Null ist, fehlt i. (Oder numerisch, wenn der Boden der Summe geteilt durch 2 ^ i gerade ist. Or sum modulo 2^(i+1)) < 2^i.)

Einfach richtig? O (N) Zeit, O (1) Speicherung, und es unterstützt beliebiges k.

Abgesehen davon, dass Sie enorme Zahlen berechnen, die auf einem realen Computer jeweils O (N) Speicherplatz benötigen würden. Tatsächlich ist diese Lösung mit einem Bitvektor identisch.

Sie könnten also klug sein und die Summe und die Summe der Quadrate und die Summe der Würfel ... bis zur Summe von v ^ k berechnen und die ausgefallene Mathematik durchführen, um das Ergebnis zu extrahieren. Aber das sind auch große Zahlen, was die Frage aufwirft: Von welchem ​​abstrakten Betriebsmodell sprechen wir? Wie viel passt in den O (1) -Raum und wie lange dauert es, Zahlen beliebiger Größe zusammenzufassen?

sfink
quelle
Gute Antwort! Eine Kleinigkeit: "Wenn sum modulo 2 ^ i Null ist, dann fehlt i" ist falsch. Aber es ist klar, was beabsichtigt ist. Ich denke "wenn sum modulo 2 ^ (i + 1) kleiner als 2 ^ i ist, dann fehlt i" wäre richtig. (Natürlich würden wir in den meisten Programmiersprachen Bitverschiebung anstelle von Modulo-Berechnung verwenden. Manchmal sind Programmiersprachen etwas ausdrucksvoller als die übliche mathematische Notation. :-))
jcsahnwaldt sagt GoFundMonica
1
Danke, du hast vollkommen recht! Behoben, obwohl ich faul war und von der mathematischen Notation abwich ... oh, und das habe ich auch durcheinander gebracht. Wieder
reparieren
1

Hier ist eine Lösung, die sich nicht auf komplexe Mathematik stützt wie die Antworten von sdcvvc / Dimitris Andreou, das Eingabearray nicht wie bei caf und Colonel Panic ändert und das Bitset von enormer Größe nicht wie Chris Lercher, JeremyP und verwendet viele andere taten es. Grundsätzlich begann ich mit der Idee von Svalorzen / Gilad Deutch für Q2, verallgemeinerte sie auf den allgemeinen Fall Qk und implementierte sie in Java, um zu beweisen, dass der Algorithmus funktioniert.

Die Idee

Angenommen, wir haben ein beliebiges Intervall I, von dem wir nur wissen, dass es mindestens eine der fehlenden Zahlen enthält. Nach einem Durchgang durch das Eingabearray , wobei wir nur die Zahlen von I betrachten , können wir sowohl die Summe S als auch die Menge Q der fehlenden Zahlen von I erhalten . Wir tun dies, indem wir einfach die Länge von I jedes Mal verringern, wenn wir auf eine Zahl von I stoßen (um Q zu erhalten ) und indem wir die vorberechnete Summe aller Zahlen in I jedes Mal um diese angetroffene Zahl verringern (um S zu erhalten ).

Nun schauen wir uns S und Q an . Wenn Q = 1 , bedeutet dies , dass dann ich enthalten nur eine der fehlenden Zahlen, und diese Zahl ist deutlich S . Wir markieren I als fertig (es wird im Programm als "eindeutig" bezeichnet) und lassen es von weiteren Überlegungen aus. Wenn andererseits Q> 1 ist , können wir den Durchschnitt A = S / Q der in I enthaltenen fehlenden Zahlen berechnen . Da alle Zahlen verschieden sind, wobei mindestens eine dieser Zahlen ist strikt kleiner als A und mindestens ein streng größer als ist A . Jetzt teilen wir mich in A.in zwei kleinere Intervalle, von denen jedes mindestens eine fehlende Zahl enthält. Beachten Sie, dass es keine Rolle spielt, welchem ​​der Intervalle wir A zuweisen, falls es sich um eine Ganzzahl handelt.

Wir machen den nächsten Array-Durchgang, indem wir S und Q für jedes der Intervalle separat berechnen (aber im selben Durchgang) und danach Intervalle mit Q = 1 markieren und Intervalle mit Q> 1 teilen . Wir setzen diesen Prozess fort, bis es keine neuen "mehrdeutigen" Intervalle mehr gibt, dh wir haben nichts zu teilen, da jedes Intervall genau eine fehlende Zahl enthält (und wir kennen diese Zahl immer, weil wir S kennen ). Wir beginnen mit dem einzigen "gesamten Bereich" -Intervall, das alle möglichen Zahlen enthält (wie [1..N] in der Frage).

Zeit- und Raumkomplexitätsanalyse

Die Gesamtzahl der Durchgänge p, die wir machen müssen, bis der Prozess stoppt, ist niemals größer als die Anzahl der fehlenden Zahlen k . Die Ungleichung p <= k kann rigoros bewiesen werden. Andererseits gibt es auch eine empirische Obergrenze p <log 2 N + 3 , die für große Werte von k nützlich ist . Wir müssen eine binäre Suche für jede Nummer des Eingabearrays durchführen, um das Intervall zu bestimmen, zu dem es gehört. Dies addiert den log k- Multiplikator zur Zeitkomplexität.

Insgesamt beträgt die zeitliche Komplexität O (N ≤ min (k, log N) ≤ log k) . Beachten Sie, dass dies für großes k signifikant besser ist als für die Methode von sdcvvc / Dimitris Andreou, die O (N ᛫ k) ist .

Für seine Arbeit benötigt der Algorithmus O (k) zusätzlichen Speicherplatz zum Speichern in den meisten k Intervallen, was in "Bitset" -Lösungen signifikant besser ist als O (N) .

Java-Implementierung

Hier ist eine Java-Klasse, die den obigen Algorithmus implementiert. Es wird immer ein sortiertes Array fehlender Zahlen zurückgegeben. Außerdem müssen die fehlenden Zahlen nicht k gezählt werden, da sie im ersten Durchgang berechnet werden. Der gesamte Zahlenbereich wird durch die Parameter minNumberund maxNumberangegeben (z. B. 1 und 100 für das erste Beispiel in der Frage).

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

Aus Fairnessgründen erhält diese Klasse Eingaben in Form von NumberBagObjekten. NumberBagErmöglicht keine Änderung des Arrays und keinen wahlfreien Zugriff und zählt auch, wie oft das Array zum sequentiellen Durchlaufen angefordert wurde. Es ist auch besser für Tests mit großen Arrays geeignet, als Iterable<Integer>weil es das Boxen primitiver intWerte vermeidet und das Umwickeln eines Teils eines großen int[]Werts für eine bequeme Testvorbereitung ermöglicht. Es ist nicht schwer zu ersetzen, falls gewünscht, NumberBagdurch int[]oder Iterable<Integer>in dem Typ findSignatur, die von zwei wechselnden for-Schleifen in ihnen in foreach denjenigen.

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

Tests

Nachfolgend finden Sie einfache Beispiele für die Verwendung dieser Klassen.

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

Tests mit großen Arrays können folgendermaßen durchgeführt werden:

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Probieren Sie sie auf Ideone aus

John McClane
quelle
0

Ich glaube, ich habe einen O(k)Zeit- und O(log(k))Raumalgorithmus, vorausgesetzt, Sie haben die floor(x)und log2(x)-Funktionen für beliebig große ganze Zahlen zur Verfügung:

Sie haben eine k-bit lange Ganzzahl (daher das log8(k)Leerzeichen), in der Sie die x^2Zahl hinzufügen , wobei x die nächste Zahl ist, die Sie in der Tasche finden: s=1^2+2^2+...Dies braucht O(N)Zeit (was für den Interviewer kein Problem ist). Am Ende erhalten Sie j=floor(log2(s))die größte Zahl, die Sie suchen. Dann s=s-jund du machst nochmal das oben genannte:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Jetzt haben Sie normalerweise keine 2756Floor- und Log2-Funktionen für -bit-Ganzzahlen, sondern für Doubles. Damit? Sie können diese Funktionen einfach für jeweils 2 Bytes (oder 1, 3 oder 4) verwenden, um die gewünschten Zahlen zu erhalten. Dies erhöht jedoch die O(N)Zeitkomplexität

CostasGR43
quelle
0

Das mag dumm klingen, aber bei dem ersten Problem, das Ihnen präsentiert wird, müssten Sie alle verbleibenden Zahlen in der Tasche sehen, um sie tatsächlich zu addieren und die fehlende Zahl anhand dieser Gleichung zu finden.

Da Sie also alle Zahlen sehen können, suchen Sie einfach nach der fehlenden Zahl. Gleiches gilt, wenn zwei Zahlen fehlen. Ziemlich einfach finde ich. Es macht keinen Sinn, eine Gleichung zu verwenden, wenn Sie die in der Tasche verbleibenden Zahlen sehen.

Stephan M.
quelle
2
Ich denke, der Vorteil der Zusammenfassung besteht darin, dass Sie sich nicht merken müssen, welche Zahlen Sie bereits gesehen haben (z. B. gibt es keinen zusätzlichen Speicherbedarf). Andernfalls besteht die einzige Möglichkeit darin, einen Satz aller angezeigten Werte beizubehalten und diesen Satz dann erneut zu durchlaufen, um den fehlenden zu finden.
Dan Tao
3
Diese Frage wird normalerweise unter der Bedingung der Komplexität des O (1) -Raums gestellt.
Die Summe der ersten N Zahlen ist N (N + 1) / 2. Für N = 100 ist Summe = 100 * (101) / 2 = 5050;
Tmarthal
0

Ich denke, das kann so verallgemeinert werden:

Bezeichnen Sie S, M als Anfangswerte für die Summe von arithmetischen Reihen und Multiplikationen.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Ich sollte über eine Formel nachdenken, um dies zu berechnen, aber das ist nicht der Punkt. Wenn eine Nummer fehlt, haben Sie die Lösung bereits bereitgestellt. Wenn jedoch zwei Zahlen fehlen, bezeichnen wir die neue Summe und das Gesamtmultiplikator mit S1 und M1, die wie folgt lauten:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Da Sie S1, M1, M und S kennen, ist die obige Gleichung lösbar, um a und b, die fehlenden Zahlen, zu finden.

Nun zu den drei fehlenden Zahlen:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Jetzt ist Ihr Unbekannter 3, während Sie nur zwei Gleichungen haben, aus denen Sie lösen können.

Jack_of_All_Trades
quelle
Die Multiplikation wird jedoch ziemlich groß. Wie verallgemeinern Sie auch auf mehr als 2 fehlende Zahlen?
Thomas Ahle
Ich habe diese Formeln in einer sehr einfachen Reihenfolge mit N = 3 und fehlenden Zahlen = {1, 2} ausprobiert. Ich habe nicht gearbeitet, da ich glaube, dass der Fehler in den Formeln (2) liegt, die lauten sollten M1 = M / (a * b)(siehe diese Antwort ). Dann funktioniert es gut.
dma_k
0

Ich weiß nicht, ob dies effizient ist oder nicht, aber ich möchte diese Lösung vorschlagen.

  1. Berechnen Sie xor der 100 Elemente
  2. Berechnen Sie xor der 98 Elemente (nachdem die 2 Elemente entfernt wurden)
  3. Jetzt (Ergebnis von 1) XOR (Ergebnis von 2) gibt Ihnen das xor der beiden fehlenden Nos i..ea XOR b, wenn a und b die fehlenden Elemente sind.
    4. Erhalten Sie die Summe der fehlenden Nos mit Ihrem üblichen Ansatz von Summenformel diff und sagen wir, der Diff ist d.

Führen Sie nun eine Schleife aus, um die möglichen Paare (p, q) zu erhalten, die beide in [1, 100] liegen und zu d summieren.

Wenn ein Paar erhalten wird, prüfen Sie, ob (Ergebnis von 3) XOR p = q ist und ob wir fertig sind.

Bitte korrigieren Sie mich, wenn ich falsch liege, und kommentieren Sie auch die zeitliche Komplexität, wenn dies korrekt ist

user2221214
quelle
2
Ich denke nicht, dass die Summe und xor zwei Zahlen eindeutig definieren. Das Ausführen einer Schleife, um alle möglichen k-Tupel zu erhalten, die sich zu d summieren, benötigt die Zeit O (C (n, k-1)) = O (nk-1), was für k2, ist schlecht.
Teepeemm
0

Wir können Q1 und Q2 die meiste Zeit in O (log n) ausführen.

Angenommen, unser memory chipbesteht aus einem Array von nAnzahl von test tubes. Und eine Zahl xim Reagenzglas wird durch x milliliterchemische Flüssigkeit dargestellt.

Angenommen, unser Prozessor ist a laser light. Wenn wir den Laser anzünden, durchläuft er alle Röhren senkrecht zu seiner Länge. Jedes Mal, wenn es durch die chemische Flüssigkeit gelangt, wird die Leuchtkraft um verringert 1. Und das Licht bei einer bestimmten Milliliter-Marke zu passieren, ist eine Operation von O(1).

Wenn wir nun unseren Laser in der Mitte des Reagenzglases anzünden und die Helligkeitsleistung erhalten

  • gleich einem vorberechneten Wert (berechnet, wenn keine Zahlen fehlten), dann sind die fehlenden Zahlen größer als n/2.
  • Wenn unsere Ausgabe kleiner ist, fehlt mindestens eine Zahl, die kleiner als ist n/2. Wir können auch überprüfen, ob die Leuchtkraft um 1oder verringert ist 2. Wenn es bis dahin reduziert wird, 1ist eine fehlende Zahl kleiner als n/2und die andere größer als n/2. Wenn es bis dahin reduziert 2ist, sind beide Zahlen kleiner als n/2.

Wir können den obigen Vorgang immer wieder wiederholen und unsere Problemdomäne eingrenzen. In jedem Schritt verkleinern wir die Domain um die Hälfte. Und schließlich können wir zu unserem Ergebnis gelangen.

Erwähnenswerte parallele Algorithmen (weil sie interessant sind),

  • Das Sortieren nach einem parallelen Algorithmus, beispielsweise das parallele Zusammenführen, kann zeitlich erfolgen O(log^3 n). Und dann kann die fehlende Nummer durch binäre Suche O(log n)rechtzeitig gefunden werden.
  • Wenn wir nProzessoren haben, kann theoretisch jeder Prozess eine der Eingaben überprüfen und ein Flag setzen, das die Nummer identifiziert (bequem in einem Array). Und im nächsten Schritt kann jeder Prozess jedes Flag überprüfen und schließlich die Nummer ausgeben, die nicht markiert ist. Der gesamte Prozess wird einige O(1)Zeit dauern . Es hat zusätzlichen O(n)Platz- / Speicherbedarf.

Beachten Sie, dass die beiden oben bereitgestellten parallelen Algorithmen möglicherweise zusätzlichen Speicherplatz benötigen, wie im Kommentar erwähnt .

Shuva
quelle
Obwohl die Reagenzglas-Laser-Methode wirklich interessant ist, hoffe ich, dass Sie damit einverstanden sind, dass sie sich nicht gut in Hardware-Anweisungen übersetzen lässt und daher kaum O(logn)auf einem Computer zu finden ist.
SirGuy
1
Was Ihre Sortiermethode betrifft, wird dies eine Menge zusätzlichen Speicherplatzes erfordern N, der von und mehr als der O(N)Zeit (in Bezug auf die Abhängigkeit von N) abhängt , was wir besser machen wollen als.
SirGuy
@SirGuy Ich schätze Ihre Besorgnis über das Reagenzglaskonzept und die Speicherkosten für die Parallelverarbeitung. Mein Beitrag ist es, meine Gedanken über das Problem zu teilen. GPU-Prozessoren machen jetzt eine Parallelverarbeitung möglich. Wer weiß, ob das Reagenzglaskonzept in Zukunft nicht mehr verfügbar sein wird.
Shuva