Jak rozwiązać zadanie, aby złożoność obliczeniowa była jak najmniejsza?

0

Dostałem ostatnio takie zadanie i z ciekawości zastanawiam się jak je rozwiązać, żeby złożoność obliczeniowa była jak najmniejsza.

Mamy dość sporą tablicę liczb typu int. Tablica jest nieposortowana i każdy element w tablicy poza jednym ma parę w postaci tej samej wartości,
czyli np {1, 2, 1, 3, 2} i trzeba znaleźć liczbę która nie ma pary.

Ja rozwiązałem to poprzez przerzucenie wartośći tablicy do HashMapy typu generycznego < Integer, Integer >
kluczem jest liczba a wartością ile razy wystąpiła. Na końcu przeglądam mapę w poszukiwaniu liczby która wystąpiła raz.

Macie jakiś lepszy pomysł? :)

0
  1. Tworzysz obiekt typu ArrayList<int>
  2. Lecisz pętlą po tablicy i sprawdzasz czy liczba jest już dodana, jeśli nie to dodajesz, jeśli tak to usuwasz.
  3. Na końcu pętli powinna zostać tablica z jednym elementem, tym który nie ma pary.
0

Chyba już nic lepszego się nie znajdzie nie? :)

1

Tworzysz pusty HashSet i iterujesz po tablicy: sprawdzasz czy element istnieje w secie - jeśli nie to wrzucasz element do seta, jeśli istnieje to go wyrzucasz. Na końcu masz set z jednym elementem.

Minimalnie wydajniejsze od Twojego powinno być, a na pewno ładniejsze ;)

EDIT: Nie zauważyłem poprzednich odpowiedzi. Idea ta sama, ale za używanie do tego ArrayList powinno się bić po twarzy.

3

Z moich eksperymentów wynika, że szybszy jest kod bez sprawdzania czy element jest w secie.

if(!set.remove(i))
    set.add(i);

jest szybsze niż

if(set.contains(i))
    set.remove(i);
else    
    set.add(i);
7
bakeraw2 napisał(a):

Chyba już nic lepszego się nie znajdzie nie? :)

Ależ skąd:

import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] tb={1, 2, 1, 3, 2};
        int result=0;
        for(int i:tb) result^=i;
        System.out.println(result);
    }
}

http://ideone.com/gcLhTy

0

Najszybszym znanym mi sposobem rozwiazania tego typu problemu jest Bloom filter

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0