Element in Folge suchen

[bRainLaG]

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.

P.S. Ich suche nicht nach dem Teilen und Herrschen Prinzip, das habe ich schon gelöst, sondern einen "naiven" Ansatz

Cheers
bRaini

 

[XHelp]

Liste sortieren und das Element in der Mitte ausgeben lassen. Warum?
Wenn es mehr als n/2 mal vorkommt, dann nimmt er über die Hälfte des Arrays ein - dieses Element steht definitiv in der Mitte.
... nur so spontag gesagt... gibts bestimmt was cooleres.

 

[bRainLaG]

Wie ich bereits erklärt habe, das ist der Teilen und Herrschen Ansatz --> siehe Quicksort
ich muss nach Aufgabe noch einen naiven Ansatz finden.
Das Teilen und Herrschen Prinzip habe ich ja schon implementiert.

 

[LadyMilka]

man könnte zählen wie oft das erste Element vorkommt, ist diese Anzahl kleiner als n/2 verwerfen, dann das zweite element nehmen und zählen usw...

 

[SlaterB]

@XHelp
dummerweise ist Sortierung nicht möglich, es gibt nur die equals-Methode, kein compare,

@bRainLaG
> und zum anderen glaube ich das es Lücken gibt, wenn ich zu viele verschiedene Elemente habe.
wieso gerade bei 'zu vielen'?, bei 4 oder 5 gehts noch, bei 9 oder 10 dann nicht mehr? das ist keine besonders robuste Eigenschaft eines Algorithmus, sowas hat man normalerweise auch nicht,

je mehr desto langsamer, ansonsten ist deine Idee erstmal richtig, klingt auch schön 'naiv' was immer du damit meinst bei Algorithmen

 

[XHelp]

Was hat denn die Art des Sortierverfahrens mit der Lösung der Aufgabe zu tun?
Wenn es wirklich sooo wichtig ist, dann nimm doch Bubblesort.
Ansonsten eben über Counter... du brauchst ja nur höhstens n/2-Werte im Counter speichern.

 

[XHelp]

@XHelp
dummerweise ist Sortierung nicht möglich, es gibt nur die equals-Methode, kein compare,

Ok, das macht Sinn... ziehe dann meinen Vorschlag zurück

 

[bRainLaG]

Danke Lady Milka das kann ich verwenden,
das Problem beim sortieren ist halt, das nicht gegeben ist, was diese Elemente sind zB, Eier lassen sich halt schwer nach etwas sortieren, mittels Sortier-Algorithmen.
Das was Lady Milka geschrieben hat könnte der naive Ansatz sein den ich brauche vielen vielen Dank