Gegeben ein array von ganzen zahlen, finden Sie die erste ganze Zahl, die einzigartig ist

Gegeben ein array von ganzen zahlen, finden Sie die erste ganze Zahl, die einzigartig ist.

meine Lösung: verwenden Sie std::map

stellen integer (Zahl als Schlüssel, den index als Wert) eines (O(n^2 lgn)), wenn Sie doppelte, entfernen Sie den Eintrag aus der map (O(lg n)), nachdem man alle zahlen in der Karte, Durchlaufen Karte und den Schlüssel finden, mit dem kleinsten index O(n).

O(n^2 lgn) weil die Karte braucht Sortierung zu tun.

Es ist nicht effizient.

andere bessere Lösungen?

  • Wenn Sie sagen, "erste ganze Zahl, die einzigartig ist" meinst du den ersten Auftritt oder den kleinsten eine, oder Zufall?
  • Das addieren aller zahlen in einer Karte ist O(n log(n)), nicht O(n^2 log(n)). Jeder Einschub ist O(log(n)), und es gibt n von Ihnen.
  • hat die neue Lösung matchup auf deine Frage, oder habe ich da etwas verpasst?
InformationsquelleAutor user1002288 | 2011-10-26
Schreibe einen Kommentar