+1, писал то же самое. В зависимости от компилятора, на С++ можно использовать либо С++11 контейнеры (unordered_set), либо из пространства имен tr1 на более старых компиляторах, если такое присутствует. По сути, при решении в лоб, придется хранить как минимум половину значений, либо хранить как-то более хитро.
Чуть подумал: проблему с памятью можно обойти, если разрешено обходить числа не последовательно, а в случайном порядке.
Также можно воспрользоваться принципом «разделяй и властвуй», т.е. строить вышеописанным способом множества элементов без пары для небольших кусков исходного массива, а потом искать симметрическую разность (объединение без пересечения) этих множеств.
Так вы еще их в массив сохраняете? Сразу сохраняйте в используемую структуру при считывании (set, unordered_set, unordered_map — в tr1 точно есть).