• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

VPS Starter Arubacloud
0 głosów
225 wizyt
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ź

0 głosów
odpowiedź 2 kwietnia 2018 przez Wiciorny Ekspert (269,120 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 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 (269,120 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. 

Podobne pytania

0 głosów
1 odpowiedź 478 wizyt
pytanie zadane 9 maja 2016 w C i C++ przez gsharp Początkujący (280 p.)
+1 głos
1 odpowiedź 533 wizyt
0 głosów
2 odpowiedzi 715 wizyt

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...