Ich muss einen hochoptimierten Algo finden, um ein Array zu sortieren, das nur aus 0s n 1s besteht.
Meine Version der Lösung besteht darin, die Nummer zu zählen. von Nullen (sagen Sie x) und Einsen (sagen Sie y). Sobald Sie das getan haben, setzen Sie x Nullen in das Array, gefolgt von y 1s. Dies macht es O (n).
Irgendein Algo, der besser als das läuft ??? Diese Frage wurde mir im Interview gestellt.
Wir können nicht besser als O (n), aber es sieht so aus, als könnten wir es in einem Durchgang machen
%Vor%Wenn Sie das Array summieren, könnten Sie die Anzahl der 1en haben, etwas effizienter, aber immer noch O (n).
Von welcher Art von "Array" reden wir? Wenn wir die Bits in einer 16-Bit-Ganzzahl ohne Vorzeichen zählen würden, dann wurden mehrere O (1) -Zeitalgorithmen entwickelt: siehe Schnelle Bit-Zählroutinen .
Dies ist einer der dort vorgestellten Algorithmen; die eine, die sie die geschickte parallele Zählung nennen:
%Vor%Das klingt wie eine Abakus-Art mit einem Stab. Jetzt bin ich neugierig, wer dein Interviewer war.