Loading...
Jovanna avatar Jovanna 186 Точки

JA1 - Задача 4 Roxettes - друга версия?

Чудя се, ако се търси уникален елемент, но появата на всички останали , освен четен брой е и нечетен, как може да стане ? XOR май няма да помогне тук... //и пак да е бързо и с малко памет

Примерно aaaaabbbbb22222bbbbb22222bbbbb

 

Тагове:
0
C++ Fundamentals 09/12/2017 14:48:17
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Здравей,

Бих казал, че не е възможно да се направи решение за по-генерализирана задача. Има вариант на тази задача с 2 уникални числа (и всички други четен брой пъти), но ако повтарящите се числа не се срещат четни броеве пъти - не става.

До голяма степен задачата се върти около особените свойства на XOR. Когато тези свойства не могат да се ползват, няма супер-ефикасно решение на задачата - налага се по някакъв начин да се пази информация кои числа се срещат и кои не.

Един вариант е да се пази масив с размер най-голямото възможно число +1 и се отбелязва бройката срещания на всяко число в елемента със съответстващ индекс (показвах ви нещо подобно на лекцията) - това е линейна сложност (всъщност сложността е O(N + maxNum), където N е броят числа и maxNum е най-голямото възможно число, тоест размера на масива, в който отбелязваш срещания), но ползва много памет.

Друг вариант е в един set (ще го учим на 12 декември) да се пазят числата, които са срещани само веднъж (и да се изваждат оттам ако бъдат срещнати отново) - този вариант е О(N*log(N)) грубо и паметта в най-лошия случай е около N/2.

Това са генерализирани варианти на задачата, ако се знае нещо особено за числата и може да се навърже с някое свойство на някоя операция, би могло да има по-ефикасно решение. Но в генералния случай (и по-често срещаното в практиката) задачата ще изисква подхода със set-а.

Поздрави,

Жоро

2
MartinBG avatar MartinBG 4803 Точки

Жоро е отговорил как стоят нещата по-принцип, но конкретно за ограниченията на тази задача има решение, което отговаря на твоя въпрос. smiley

Стигнах до него в предишното издание на курса след една нощ главоблъскане. Решението не e алгоритмично, колкото решениетo с XOR, но пък използва една по-малко известна структура - bitset.

Като логика, това решение комбинира XOR решението и решението с използане на масив, в който индексите отговарят на конкретно число, а стойността - на броя срещане на това число във входните данни.

Най-общо - за всяко число във входните данни се инвертира стойността (бит, т.е. 1 или 0) на индекса, който отговаря на това число. Накрая се обхожда битсет-а, като всеки индекс, чиято стойност е 1 означава, че това число е било намерено нечетен брой пъти във входните данни. Алгоритъмът е по-скоро с линейна сложност (N + maxNum).

Пишете като мине срока за това домашно и ще си постна кода на решението тук.

 

 

EDIT:

Сега ти прочетох по-внимателно въпроса и виждам, че съм отговорил на друг въпрос. :)

Ако търсиш всички числа, които се срещнат само веднъж във входните данни, най-простото решение е да използваш масив, на който индексите отговарят на числата, а стойностите в масива - на броя срещания във входните данни. Накрая изкарваш само тези индекси, чиито стойности в масива са 1. Това е и първото решение, което е написал Жоро.

Втората му идея (с set) не успявам да си я представя при вариант, в който числото се среща повече от 2 пъти (при първата среща го добавяме в set-a, при втората - го махаме и при третата ще го добавим отново, защото нямаме знанието, че вече е срещано), но сигурно отново изпускам нещо. :)

 

ЕDIT 2:

В някои случаи (входни данни, които не са числа или пък числа, по-големи от size_t или при широк диапазон на входните данни, но малко на брой уникални стойности, комбинирано с ограниение в паметта), може използването на map вместо масив да е по-подходящото решение.

1
09/12/2017 22:55:13
Jovanna avatar Jovanna 186 Точки

Пробвах с bitset, не ми минаха половината тестове, Жоро е сложил перфектните ограничения за памет (и бързодействие).

На половината тестове гърми, защото трябва да направиш променлива std::bitset<32> resultBinaryEcsclusiveOr заради fffff - с 5 символна последователност най-дългото binarno представяне е 20 нули/единици;

Може би тук ще върви подсказката , че половината от тестовете са с малки числа, до 10000, което е 16 броя 0/1 и ще стане с std::bitset<16>, + една проверка числото дали е <= 10000, едно switch-че , еднакъв код два пъти, с единствена разлика обема на bitset променливата.

Незнам в подробности как се работи с bitset, за това което правя чета в нета, може и да бъркам?

Ще го учим ли?

0
MartinBG avatar MartinBG 4803 Точки

Моето решение с bitset минава в Judge с тези резултати:

Memory: 1.96 MB 
Time: 0.642 s

Сета ми е с тези параметри:

const int MAX_DNA_TYPES = 0xFFFFF;

int main()
{
    std::bitset<MAX_DNA_TYPES> uniqueDNA;
...
}

 

1
MartinBG avatar MartinBG 4803 Точки

Ето решението ми с bitset, в случай, че все още представлява интерес.

(линка ще expire-не след 1 месец).

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.