Hallo ich setze mich grade mit folgendem Problem auseinander:
Gegeben sei eine Folge von n Elementen. Sie haben ein Verfahren, mit dem Sie je zwei Elemente auf Gleichheit oder Ungleichheit testen ko ?nnen, und Sie wissen, dass ein Element echt mehr als n/2 mal in dem Feld vorkommt. Dieses Element gilt es zu bestimmen.
Dafür fehlt mir noch der naive Algorithmus, ich habe überlegt es so zu machen, das erste Element zu wählen und jedesmal wenn es vorkommt, einen Counter um 1 hochzählen zu lassen, nach dem die Folge durchlaufen wurde, das zweite Element nehmen, gucken ob es mit dem vorigen übereinstimmt, und falls nicht einen weiteren Counter erstellen.
Das ganze erscheint mir einerseits Laufzeitmäßig sehr schwach, und zum anderen glaube ich das es Lücken gibt, wenn ich zu viele verschiedene Elemente habe.
Ich habe nun die Frage ob jemand nen Tipp hat wie man diesen naiven Ansatz besser angehen kann.
Cheers
Ralf
Gegeben sei eine Folge von n Elementen. Sie haben ein Verfahren, mit dem Sie je zwei Elemente auf Gleichheit oder Ungleichheit testen ko ?nnen, und Sie wissen, dass ein Element echt mehr als n/2 mal in dem Feld vorkommt. Dieses Element gilt es zu bestimmen.
Dafür fehlt mir noch der naive Algorithmus, ich habe überlegt es so zu machen, das erste Element zu wählen und jedesmal wenn es vorkommt, einen Counter um 1 hochzählen zu lassen, nach dem die Folge durchlaufen wurde, das zweite Element nehmen, gucken ob es mit dem vorigen übereinstimmt, und falls nicht einen weiteren Counter erstellen.
Das ganze erscheint mir einerseits Laufzeitmäßig sehr schwach, und zum anderen glaube ich das es Lücken gibt, wenn ich zu viele verschiedene Elemente habe.
Ich habe nun die Frage ob jemand nen Tipp hat wie man diesen naiven Ansatz besser angehen kann.
Cheers
Ralf