[Y.....m]

#nukaprogramowania #java #programowanie

Robię zadania z codility. Zatrzymałem się na 2.2. chodzi tam o wyszukanie z tablicy jednej liczby, która się nie powtarza ani razu. Tablica składa się z nieparzystej liczby liczb, wszystkie się dublują oprócz jednej.

Mój algorytm:

- posortowanie tablicy od najmniejszej liczby do największej
- Sprawdzenie, czy pierwsza cyfra jest taka sama, jak następna ->
a) jeśli nie, wynik to pierwsza liczba
b) jeśli tak ->
c) sprawdzenie, czy ostatnia liczba jest taka sama, jak poprzednia -> jeśli nie, wynik to ostatnia liczba

Następnie przeszukanie tablicy od pierwszego indeksu i wyszukanie liczby, która jest inna niż liczba poprzednia i inna niż liczba następna.

Niestety niektóre testy nie przechodzą i wydajność jest na 60%. Co robię źle i jak usprawnić algorytm?

[WhiskyRomeo]

@YourDoom: a nie możesz użyć hashmapy i przelecieć się tylko raz? Przechowujesz każda liczbę w hash mapie i sprawdzasz czy wystąpiła. Na koniec sprawdzasz hashmapy która wartość jest równa jeden i wynikiem jest klucz tej wartości.

[Y.....m]

@WhiskyRomeo: mogę, ale myślałem, że tworzenie nowej struktury danych to gorsza wydajność? U mnie też tylko raz leci pętla w poszukiwaniu liczby

[63274682374]

mogę, ale myślałem, że tworzenie nowej struktury danych to gorsza wydajność? U mnie też tylko raz leci pętla w poszukiwaniu liczby

@YourDoom: sortowanie zajmuje o wiele więcej czasu niż utworzenie obiektu.

[63274682374]

2. Dodając do set, sprawdz czy taki element juz istnieje metodą contains() (stały czas dostępu), jeśli już istnieje usuń (stały czas usunięcia)

@zapalara: Kosmetycznie można to poprawić i zamiast sprawdzać contains() zawsze dodawać i jeśli metoda add zwróci true, wtedy usuwać.

[zapalara]

@63274682374: o właśnie nie pamiętałem jakie to tam API w javie jest, czy rzuca exception czy zwraca bool'a. Spoko

[63274682374]

PS można to bez struktur danych zrobić, ale jeszcze muszę sprawdzić

@63274682374: Wystarczy użyć xora.

 int[] i = new int[]{2,4,5,6,2,8,5, 4,6 , 7 ,7 };
 int result

[zapalara]

@WhiskyRomeo: klucze w mapie mają c, wartości po n, tak jak @63274682374 napisał

Też obstawiam że to się da bez struktur zrobić, jakiś fajny trick, nie wpadłem na nic na szybko. Jakbys cos wykminil to podziel sie

[zapalara]

@63274682374: teraz to takie oczywiste :) Piękna robota @63274682374 Jakbys szukał pracy daj znać :)