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

pytanie zadane 1 kwietnia 2018 w Android, Swift, Symbian przez miriv Nowicjusz (120 p.)

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.

1 odpowiedź

odpowiedź 2 kwietnia 2018 przez Wiciorny Ekspert (270,190 p.)

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 ]

komentarz 2 kwietnia 2018 przez Aisekai Nałogowiec (42,190 p.)

O ile dobrze zrozumiałem, to jest pewien zasadniczy problem: Co w przypadku gdy powtarzających się elementów będzie nieparzysta liczba razy w tablicy?

komentarz 2 kwietnia 2018 przez Wiciorny Ekspert (270,190 p.)

które się powtarzają, tylko jedna cyfra się nie powtarza

Taki był cel zadania, więc dla przykładu który został przez kolege podany ten sposób zadziała. jednak dla przypadku "będzie nieparzysta liczba razy" rozumiem, że chodzi Ci o to, że dany element wystąpi nieparzyście- wtedy fakt będzie źle, natomiast zauwaz że ja podałem tylko schemat ( dodatkowo utrzył bym w tym samym czasie dodatkową liste, przechowującą już elementy które wystąpiły :) i sprawdzał warunek zanim dodam do kolejki )... ale to działa wtedy nadal jeśli poszukujemy 1 ELEMENTU

doda, że taki warunek sprawdzajacy czy element obecny " był już w kolejce, i czy lub się powtarza można uwzględnić w jednym warunku )

To jest troszeczke podobne zadanie do przeglądania BFS ALGORYTMU NP. NA GRAFIE w oparciu o implementacje na bazie kolejki

komentarz 2 kwietnia 2018 przez Aisekai Nałogowiec (42,190 p.)

Tak, chodziło mi o to że np w tablicy dana liczba wystąpi nieparzystą liczbę razy, ale więcej niż raz.

Pomysł fajny, z tym żeby utworzyć kolejkę i dodać do niej element, a jeśli znalazloby się potem taki sam element to usunąć go.

Tylko tutaj się rodzi kolejne pytanie, czy taki algorytm rzeczywiście będzie nlogn i czy nie prościej (na pewno w implementacji) byłoby po prostu quicksortem posortowac (nlogn) i potem szukać tego elementu.

komentarz 2 kwietnia 2018 przez miriv Nowicjusz (120 p.)

Hmm koncepcja fajna, tylko jak ja to mogę napisać w Swifcie ? :)

Próbowałem stworzyć nową tablice, gdzie będę dodawał nowe elementy i usuwał te, które się powtarzają, ale jakoś średnio to działa, bo sprawdzany element jest tym samym co dodawany.

Napiszecie przykład kodu jak by to mogło działać?

Z góry dzięki :)

komentarz 2 kwietnia 2018 przez Wiciorny Ekspert (270,190 p.)

@Aisekai, samo sortowanie quicksortem jest wstawianie (O(n2)). więc to już odpada

komentarz 2 kwietnia 2018 przez Aisekai Nałogowiec (42,190 p.)

W pesymistycznym przypadku. Średnia złożoność obliczeniowa (a taką się podaje jak mówimy o złożoności obliczeniowej) jest rzędu O(nlogn).

komentarz 2 kwietnia 2018 przez miriv Nowicjusz (120 p.)

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

komentarz 2 kwietnia 2018 przez Aisekai Nałogowiec (42,190 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.

komentarz 2 kwietnia 2018 przez Wiciorny Ekspert (270,190 p.)

@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

komentarz 2 kwietnia 2018 przez mokrowski Mędrzec (155,460 p.)

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 :)

komentarz 3 kwietnia 2018 przez Aisekai Nałogowiec (42,190 p.)

@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.