Anzahl unterschiedlicher Elemente zählen

[Saheeda]

Hallo,

vielleicht könnt ihr mir ja helfen. Ich hab ne Aufgabe bekommen, weiß aber nicht so richtig, wie ich ansetzen soll:


"Die Zahlen einer Liste sind aufsteigend sortiert. Aufgabe ist, zu zählen, wie viele unterschiedliche Elemente es gibt. Der Knackpunkt ist, dass der Algorithmus die Lösung in linearer Zeit finden soll (O(x)). Das bedeutet, die Triviallösung, alle Elemente in ein Set zu packen, und am Ende die Länge des Sets zu ermitteln (new HashSet(sortedListOfNumbers).size()) nicht dieser Anforderung genügt - Sie kann aber als generische Kontrollfunktion verwendet werden."

Ich weiß dank Google inzwischen, dass die O-Notation verwendet wird, um die Laufzeit eines Programmes/Algortihmus' zu messen und dass es verschiedene Sortieralgorithmen (z.B.Quicksort) gibt, um auch große Datensätze möglichst schnell durchlaufen zu lassen.



Meine Idee wäre, die Liste zunächst, ähnlich wie bei Quicksort, auf zwei oder bei großen Mengen mehr HashSets zu teilen (um zumindest schonmal die Hälfte aller Duplikate zu eliminieren) und mit addAll wieder zusammenzuführen.
Ich habe aber nicht das Gefühl, dass das so viel Zeit spart beim Ausführen.


Kann mir jemand vielleicht beim Ansatz helfen?

 

[Thallius]

Int[] zahlen.....
Int last=-1;
Int count=0;
For(int y=0;y<zahlen.length;y++)
{
    If(zahlen[y]!=last)
    {
        count++;
        last=zahlen[y];
     }
}

Gruss

Claus

 

[Saheeda]

Hallo Claus,

so einfach ist das? :autsch: Wieder mal viel zu kompliziert gedacht...

Danke.

 

[Thallius]

Setzt natürlich voraus das das Array der Zahlen aufsteigend sortiert ist aber das hättest du ja geschrieben.

Gruss

Claus

 

[Hobbes]

Und ein Fall ist nicht korrekt abgedeckt. Das überlasse ich aber Saheeda als Übung.