Ermitteln, ob im Array eine Zahl existiert, die k mal vorkommt

Question

Ich möchte einen Divide and Conquer-Algorithmus (O (nlgn) runtime) erstellen, um festzustellen, ob in einem Array eine Zahl k mal vorkommt. Eine Einschränkung für dieses Problem besteht darin, dass für die Objekte des Arrays nur eine Vergleichsmethode für Gleichheit/Ungleichheit definiert ist (d. H. <,> kann nicht verwendet werden).

Also habe ich eine Reihe von Ansätzen ausprobiert, einschließlich der Aufspaltung des Arrays in k Stücke gleicher Größe (ungefähr). Der Ansatz ähnelt dem Finden des Mehrheitselementes in einem Array. Wenn Sie jedoch das Array teilen, wissen Sie, dass die Mehrheit einen Majoritätseintrag haben muss, wenn ein solches Element existiert. Irgendwelche Hinweise oder Tipps, die man mir geben könnte, um mich in die richtige Richtung zu bringen?

EDIT: Um ein wenig aufzuräumen, frage ich mich, ob das Problem des Findens der Majorität Element durch Aufspalten des Arrays in zwei Hälften und Verwenden einer rekursiven Lösung auf andere Situationen erweitert werden kann, wobei k n/4 oder n/sein kann 5 usw.

Vielleicht sollte ich die Frage mit n/k stattdessen phrasen.

Answer 1

Dies ist unmöglich. Als einfaches Beispiel dafür, warum dies nicht möglich ist, betrachte man eine Eingabe mit einem length-n-Array, wobei alle Elemente verschieden sind und k = 2 ist. Die einzige Möglichkeit, sicher zu sein, dass kein Element zweimal auftritt, ist, jedes Element mit jedem anderen Element zu vergleichen, das die Zeit O (n^2) benötigt. Bis Sie alle möglichen Vergleiche durchgeführt haben, können Sie nicht sicher sein, dass ein Paar, das Sie nicht verglichen haben, nicht gleich ist.