Чудя се, ако се търси уникален елемент, но появата на всички останали , освен четен брой е и нечетен, как може да стане ? XOR май няма да помогне тук... //и пак да е бързо и с малко памет
Примерно aaaaabbbbb22222bbbbb22222bbbbb
Здравей,
Бих казал, че не е възможно да се направи решение за по-генерализирана задача. Има вариант на тази задача с 2 уникални числа (и всички други четен брой пъти), но ако повтарящите се числа не се срещат четни броеве пъти - не става.
До голяма степен задачата се върти около особените свойства на XOR. Когато тези свойства не могат да се ползват, няма супер-ефикасно решение на задачата - налага се по някакъв начин да се пази информация кои числа се срещат и кои не.
Един вариант е да се пази масив с размер най-голямото възможно число +1 и се отбелязва бройката срещания на всяко число в елемента със съответстващ индекс (показвах ви нещо подобно на лекцията) - това е линейна сложност (всъщност сложността е O(N + maxNum), където N е броят числа и maxNum е най-голямото възможно число, тоест размера на масива, в който отбелязваш срещания), но ползва много памет.
Друг вариант е в един set (ще го учим на 12 декември) да се пазят числата, които са срещани само веднъж (и да се изваждат оттам ако бъдат срещнати отново) - този вариант е О(N*log(N)) грубо и паметта в най-лошия случай е около N/2.
Това са генерализирани варианти на задачата, ако се знае нещо особено за числата и може да се навърже с някое свойство на някоя операция, би могло да има по-ефикасно решение. Но в генералния случай (и по-често срещаното в практиката) задачата ще изисква подхода със set-а.
Поздрави,
Жоро
Жоро е отговорил как стоят нещата по-принцип, но конкретно за ограниченията на тази задача има решение, което отговаря на твоя въпрос. 
Стигнах до него в предишното издание на курса след една нощ главоблъскане. Решението не e алгоритмично, колкото решениетo с XOR, но пък използва една по-малко известна структура - bitset.
Като логика, това решение комбинира XOR решението и решението с използане на масив, в който индексите отговарят на конкретно число, а стойността - на броя срещане на това число във входните данни.
Най-общо - за всяко число във входните данни се инвертира стойността (бит, т.е. 1 или 0) на индекса, който отговаря на това число. Накрая се обхожда битсет-а, като всеки индекс, чиято стойност е 1 означава, че това число е било намерено нечетен брой пъти във входните данни. Алгоритъмът е по-скоро с линейна сложност (N + maxNum).
Пишете като мине срока за това домашно и ще си постна кода на решението тук.
EDIT:
Сега ти прочетох по-внимателно въпроса и виждам, че съм отговорил на друг въпрос. :)
Ако търсиш всички числа, които се срещнат само веднъж във входните данни, най-простото решение е да използваш масив, на който индексите отговарят на числата, а стойностите в масива - на броя срещания във входните данни. Накрая изкарваш само тези индекси, чиито стойности в масива са 1. Това е и първото решение, което е написал Жоро.
Втората му идея (с set) не успявам да си я представя при вариант, в който числото се среща повече от 2 пъти (при първата среща го добавяме в set-a, при втората - го махаме и при третата ще го добавим отново, защото нямаме знанието, че вече е срещано), но сигурно отново изпускам нещо. :)
ЕDIT 2:
В някои случаи (входни данни, които не са числа или пък числа, по-големи от size_t или при широк диапазон на входните данни, но малко на брой уникални стойности, комбинирано с ограниение в паметта), може използването на map вместо масив да е по-подходящото решение.
Пробвах с bitset, не ми минаха половината тестове, Жоро е сложил перфектните ограничения за памет (и бързодействие).
На половината тестове гърми, защото трябва да направиш променлива std::bitset<32> resultBinaryEcsclusiveOr заради fffff - с 5 символна последователност най-дългото binarno представяне е 20 нули/единици;
Може би тук ще върви подсказката , че половината от тестовете са с малки числа, до 10000, което е 16 броя 0/1 и ще стане с std::bitset<16>, + една проверка числото дали е <= 10000, едно switch-че , еднакъв код два пъти, с единствена разлика обема на bitset променливата.
Незнам в подробности как се работи с bitset, за това което правя чета в нета, може и да бъркам?
Ще го учим ли?
Моето решение с bitset минава в Judge с тези резултати:
Memory: 1.96 MB
Time: 0.642 s
Сета ми е с тези параметри:
const int MAX_DNA_TYPES = 0xFFFFF;
int main()
{
std::bitset<MAX_DNA_TYPES> uniqueDNA;
...
}