Znalezienie elementu w tablicy, który się nie powtarza

Question

Witam,

mam taką tablice [1,2,3,4,1,2,3], są tu 3 pary, które się powtarzają, tylko jedna cyfra się nie powtarza. Chce napisać algorytm, który mi tą cyfrę znajdzie. Wiecie jak mogę takie coś napisać używając złożoności obliczeniowej nlogn??

Z góry dzięki i pozdrawiam.

Answer 1

Ja bym to napisał na przeglądaniu tablicy i wrzycaniu elementów do kolejki,  jeśli napotkasz element  po raz kolejny, usuwasz go z kolejki w ten sposób na końcu powinno znaleźć ( elementy w kolejce ) -> odpowiadające tylko jednemu wystąpieniu elementu w zbiorze liczbowym [ jeśli będzie kilka liczb tylko po 1, to wtedy kolejka bedzie miała kilka elementów ]

Comments

Mam inną koncepcje, że biorę element z tablicy i sprawdzam czy jest on w tablicy, jeśli tak to jadę dalej i zostaje tylko ten jeden element i to będzie miało złożoność nlogn.

Tylko nie wiem jak to w Swifcie mogę dobrze napisać. Jakieś pomysły? :P

---

Jesteś pewien, że to będzie miało nlogn a nie n2? Ten problem można sformułować inaczej:

"Poszukujemy liczby w zbiorze, dla której nie istnieje druga liczba w tym zbiorze, których suma będzie wynosić dwukrotnosc tej liczby" - wniosek: w przypadku pesymistycznym będziesz miał złożoność n2. A o ile dobrze pamiętam, na studiach robiliśmy taki przykład (tylko, że nie było z góry narzuconej sumy dwóch liczb, tylko szukanie dwóch elementów których suma jest równa np 9) i wyszło, że złożoność jest kwadratowa.

---

@Aisekai, jak mowa o złożoności zawsze podajemy pesymistyczną ...  z defyinicji notacji wielkiego O chociażby 

Złożoność obliczeniowa a funkcja Złożoność obliczeniową określamy jako funkcję danych wejściowych algorytmu. Wyznacza się ją jak opisałem w poprzednim punkcie - licząc operacje. O ile dla naukowców znalezienie dokładnej funkcji może być bardzo istotne, to w praktyce wystarczą jej oszacowania. Takie oszacowania to notacja Ο (dużego O), notacja Ω (omega) i notacja Θ (theta).

Więc jesli mowa o złożonośc O(nlogn) to jest to złożoność pesymistyczna z definicji funkcji 

---

Naiwne podejście to słownik w którym kluczem będzie element a wartością licznik wystąpień. Po przejrzeniu danych i inkrementacji wartości danego klucza, przeglądasz słownik i drukujesz tylko te wartości które mają licznik 1. Popatrz na złożoności i myślę że wystarczy :)

---

@Wiciorny, na studiach byłem uczony, że jeśli mamy podać złożoność obliczeniowa, to podajemy średnią. Ale jeżeli jest tak jak mówisz, to dobrze wiedzieć.  Zawsze się człowiek czegoś nowego uczy.

Dzięki.