Задача за намиране на елемент в масив


0

Здравейте, трябва ми малко помощ със следната задача:

Имаме огромен масив, в който всяко число се повтаря по два пъти, само едно число е уникално, задачата е да го намерим с възможно най малко операции, с минимална памет и минимално процсорно време. Не можем да сортираме масива. Масива е с абсолютно random стойности, без никаква подредба.

Пример: [1, 2, 3, 1, 4 2, 3]

И само насоки как да подходя биха ми били много полезни. Благодаря предварително!




Отговори



1
Xor-ваш всички числа в масива и тва което се получава е числото, което се повтаря един път. Ето ти и примерен код: https://stackoverflow.com/a/29333723/5958676. Обхождането е линейно, ^ e константно - сложност O(n).

от markshark05 (195 точки)


0
Благодаря колега!

от neznamue (0 точки)


0
Здравей колега,



масива при всички случаи трябва да бъде обходен целия (тоест сложноста на алгоритъма ти автоматично става поне О(n)).

Вървейки по масива бих вкарвал всяко число в един HashSet. Ако числото вече е в HashSet-а бих го махал от него (търсенето дали числото е в HashSet-а, вкарването и махането са все константни операции). На края на обхождането в HashSet-а ще имам само 1 число (търсеното). Worst space complexity-то е О(log n), best е O(1) (понеже не мога да имам повече от 1/2 от числата в HashSet-а).

Тоест в крайна сметка O(n) + n * O(1) = O(n).

В момента не мога да се сетя за много по-ефективен начин.



Успех!

от ggeorgievx (55 точки)


1
Worst space complexity-то на решение с HashSet или подобно е О(n). Пример:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Предлагам една стъпка по-трудна задача: Всяко число (освен търсеното) ще се повтаря кратен на K брой пъти. K е предварително известно. Отново се търси ефективно решение откъм време и памет.

от cuki (7696 точки)

0
Благодаря колега! И аз тръгнах така от начало, но все пак имаш HashSet-а дето ти е допълнително памет.

от neznamue (0 точки)