Здравствуйте, Caracrist, Вы писали:
C>первое решается элементарно, и вообще довольно так бородато, C>a какие будут продложения по (b) и (c)?
Если "в лоб" решение, то завести hash table: ключь таблицы — число, а значение счетчик сколько оно встретилось в массиве. Двигаться по массиву и класть значение в hash table. Если значение уже есть, то увеличить значение счетчика. В конце найти в hash table значения, где счетчик равен 1. Получаем O(N) по скорости и памяти.
Здравствуйте, kr510, Вы писали:
K>Если "в лоб" решение, то завести hash table: ключь таблицы — число, а значение счетчик сколько оно встретилось в массиве. Двигаться по массиву и класть значение в hash table. Если значение уже есть, то увеличить значение счетчика. В конце найти в hash table значения, где счетчик равен 1. Получаем O(N) по скорости и памяти.
Здравствуйте, Caracrist, Вы писали:
C>Есть список чисел. Все числа встречаются дважды, кроме:
C>a) одного C>b) двух C>c) трех
C>найти одиночек.
C>первое решается элементарно, и вообще довольно так бородато, C>a какие будут продложения по (b) и (c)?
Если числа 4-байтовые, очевидное решение — выделить массив на 512 MB и проходя по числам переключать соответствующий бит. В конце вывести все числа с включенным битом.
Здравствуйте, Caracrist, Вы писали:
C>найти одиночек.
C>первое решается элементарно, и вообще довольно так бородато, C>a какие будут продложения по (b) и (c)?
Вариант 1:
1. Отсортировать.
2. Пройтись и найти искомые элементы.
3. ...
4. PROFIT!
Это O(N*logN).
Вариант 2:
1. Взять первый элемент.
2. Пройтись по массиву и найти дубликат.
3. Удалить эти два элемента.
4. Повторять, пока не останутся искомые элементы.
5. ...
6. PROFIT!
Здравствуйте, Caracrist, Вы писали:
C>O(nk) — это не решение, так как k стремится к logn, это фактически nlogn
Это все зависит от исходных условий, если мы начнем считать, что k — не константа, то тогда непонятно с чего это мы решили, что xor выполняется за O(1).
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, Caracrist, Вы писали:
C>>O(nk) — это не решение, так как k стремится к logn, это фактически nlogn
_DA>Это все зависит от исходных условий, если мы начнем считать, что k — не константа, то тогда непонятно с чего это мы решили, что xor выполняется за O(1).
k = log(max(n))
уже просто nlogn лучше будет
допустим xor выполняется за O(1) — это дано.
есть ли решение не зависящее от k?
Здравствуйте, Caracrist, Вы писали:
C>k = log(max(n)) C>уже просто nlogn лучше будет
Ок, если говорить про задачу по ссылке, то там чуть более общее условие. Там нет условия "дважды", поэтому там k не равно log(max(n)). В данной задаче да, большого смысла в такой ассимптотике нет.
C>допустим xor выполняется за O(1) — это дано. C>есть ли решение не зависящее от k?
Скорость — O(n), память — O(1)? Сильно сомневаюсь, но можно еще подумать спустя 8 лет
Здравствуйте, Chorkov, Вы писали: C>Есть список чисел, в котором все числа встречаются трижды, кроме одного. C>Найти это число. C>Ограничение: O(1) по памяти, один проход по списку.
спойлер: триты
Использовать триты вместо битов.
Можно даже, чтобы не заниматься честным переводом всех чисел в троичную систему, тупо расширить каждый бит до трита, а трит — до двух бит.
Тогда арифметика получится очень простая.
Здравствуйте, Chorkov, Вы писали:
C>Здравствуйте, Caracrist, Вы писали:
C>Еще один родственный баян:
C>Есть список чисел, в котором все числа встречаются трижды, кроме одного. C>Найти это число. C>Ограничение: O(1) по памяти, один проход по списку.
Ну по идее тоже самое, просто вместо побитового сложения по модулю 2 (xor), надо делать поразрядное сложение по модулю три чисел, переведенных в троичную СС.