Найти один непо-повторяющийся элемент в массиве?

У меня есть массив из nэлементов, в котором не повторяется только один элемент, иначе все остальные числа повторяются >1 раз. И нет ограничений на диапазон чисел в массиве.

Некоторые решения::

• Использование хэша, , но это приведет к линейной временной сложности, но очень низкой пространственной сложности
• Сортировка списка с использованием MergeSort O(nlogn)и последующий поиск элемента, который не повторяется

Есть ли лучшее решение?