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

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

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.

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

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.

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

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

Najszybszym znanym mi sposobem rozwiazania tego typu problemu jest Bloom filter