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

[zapalara]

@YourDoom: po #!$%@? to sortujesz? to jest czasochlonne.

Jakiś gówniany pomysł co mi przyszedł na szybko:
1. Przeleć po całej tablicy, dodaj każdy element do Set
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)
3. Jak przelecisz całą tablice zostanie ci 1 element,

[zapalara]

@WhiskyRomeo: #!$%@?, sprawdzenie value==1 mapy bedzie zajmowało kolejną iteracje po n, to już moje gówniane rozwiązanie szybsze

[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

[WhiskyRomeo]

#!$%@?, sprawdzenie value==1 mapy bedzie zajmowało kolejną iteracje po n, to już moje gówniane rozwiązanie szybsze

@zapalara: nie #!$%@? tylko prawidłowe. Sprawdzanie hash mapy to dokładnie 1 a nie n.

[63274682374]

nie #!$%@? tylko prawidłowe. Sprawdzanie hash mapy to dokładnie 1 a nie n.

@WhiskyRomeo: kluczy 1, wartości n


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

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