Есть список чисел, найти одиночек
От: Caracrist https://1pwd.org/
Дата: 26.04.15 07:43
Оценка:
Есть список чисел. Все числа встречаются дважды, кроме:

a) одного
b) двух
c) трех

найти одиночек.


первое решается элементарно, и вообще довольно так бородато,
a какие будут продложения по (b) и (c)?

Взято тут.
~~~~~
~lol~~
~~~ Single Password Solution
Re: Есть список чисел, найти одиночек
От: kr510  
Дата: 26.04.15 08:58
Оценка:
Здравствуйте, Caracrist, Вы писали:

C>первое решается элементарно, и вообще довольно так бородато,

C>a какие будут продложения по (b) и (c)?

Если "в лоб" решение, то завести hash table: ключь таблицы — число, а значение счетчик сколько оно встретилось в массиве. Двигаться по массиву и класть значение в hash table. Если значение уже есть, то увеличить значение счетчика. В конце найти в hash table значения, где счетчик равен 1. Получаем O(N) по скорости и памяти.

Возможно есть проще решения.
Re[2]: Есть список чисел, найти одиночек
От: andy1618 Россия  
Дата: 26.04.15 10:13
Оценка:
Здравствуйте, kr510, Вы писали:

K>Если "в лоб" решение, то завести hash table: ключь таблицы — число, а значение счетчик сколько оно встретилось в массиве. Двигаться по массиву и класть значение в hash table. Если значение уже есть, то увеличить значение счетчика. В конце найти в hash table значения, где счетчик равен 1. Получаем O(N) по скорости и памяти.


Обычно в таких задачах требуется O(1) по памяти.
Re: Есть список чисел, найти одиночек
От: vsb Казахстан  
Дата: 26.04.15 12:52
Оценка:
Здравствуйте, Caracrist, Вы писали:

C>Есть список чисел. Все числа встречаются дважды, кроме:


C>a) одного

C>b) двух
C>c) трех

C>найти одиночек.



C>первое решается элементарно, и вообще довольно так бородато,

C>a какие будут продложения по (b) и (c)?

Если числа 4-байтовые, очевидное решение — выделить массив на 512 MB и проходя по числам переключать соответствующий бит. В конце вывести все числа с включенным битом.
Re: Есть список чисел, найти одиночек
От: andrey.desman  
Дата: 26.04.15 13:12
Оценка:
Здравствуйте, Caracrist, Вы писали:

C>найти одиночек.


C>первое решается элементарно, и вообще довольно так бородато,

C>a какие будут продложения по (b) и (c)?

Вариант 1:
1. Отсортировать.
2. Пройтись и найти искомые элементы.
3. ...
4. PROFIT!

Это O(N*logN).

Вариант 2:
1. Взять первый элемент.
2. Пройтись по массиву и найти дубликат.
3. Удалить эти два элемента.
4. Повторять, пока не останутся искомые элементы.
5. ...
6. PROFIT!

Это O(N^2)
Re: Есть список чисел, найти одиночек
От: _DAle_ Беларусь  
Дата: 26.04.15 16:26
Оценка: 4 (1)
Здравствуйте, Caracrist, Вы писали:

Было хотя бы тут: http://rsdn.ru/forum/etude/2312957.1
Автор: nikov
Дата: 22.01.07
Re[2]: Есть список чисел, найти одиночек
От: Caracrist https://1pwd.org/
Дата: 26.04.15 18:56
Оценка:
Здравствуйте, _DAle_, Вы писали:

_DA>Было хотя бы тут: http://rsdn.ru/forum/etude/2312957.1
Автор: nikov
Дата: 22.01.07


там ответ для (b) а как на счет (c)?
O(nk) — это не решение, так как k стремится к logn, это фактически nlogn
~~~~~
~lol~~
~~~ Single Password Solution
Отредактировано 26.04.2015 19:06 Caracrist . Предыдущая версия . Еще …
Отредактировано 26.04.2015 19:03 Caracrist . Предыдущая версия .
Re[3]: Есть список чисел, найти одиночек
От: _DAle_ Беларусь  
Дата: 26.04.15 19:10
Оценка:
Здравствуйте, Caracrist, Вы писали:

C>O(nk) — это не решение, так как k стремится к logn, это фактически nlogn


Это все зависит от исходных условий, если мы начнем считать, что k — не константа, то тогда непонятно с чего это мы решили, что xor выполняется за O(1).
Re[4]: Есть список чисел, найти одиночек
От: Caracrist https://1pwd.org/
Дата: 26.04.15 19:16
Оценка:
Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, Caracrist, Вы писали:


C>>O(nk) — это не решение, так как k стремится к logn, это фактически nlogn


_DA>Это все зависит от исходных условий, если мы начнем считать, что k — не константа, то тогда непонятно с чего это мы решили, что xor выполняется за O(1).


k = log(max(n))
уже просто nlogn лучше будет

допустим xor выполняется за O(1) — это дано.
есть ли решение не зависящее от k?
~~~~~
~lol~~
~~~ Single Password Solution
Re[5]: Есть список чисел, найти одиночек
От: _DAle_ Беларусь  
Дата: 26.04.15 19:33
Оценка: +1
Здравствуйте, Caracrist, Вы писали:

C>k = log(max(n))

C>уже просто nlogn лучше будет

Ок, если говорить про задачу по ссылке, то там чуть более общее условие. Там нет условия "дважды", поэтому там k не равно log(max(n)). В данной задаче да, большого смысла в такой ассимптотике нет.

C>допустим xor выполняется за O(1) — это дано.

C>есть ли решение не зависящее от k?

Скорость — O(n), память — O(1)? Сильно сомневаюсь, но можно еще подумать спустя 8 лет
Re[6]: Есть список чисел, найти одиночек
От: Caracrist https://1pwd.org/
Дата: 28.04.15 13:05
Оценка:
Здравствуйте, _DAle_, Вы писали:

_DA>Скорость — O(n), память — O(1)? Сильно сомневаюсь


ну мы оба понимаем, что врядли на том ресурсе вопрос задали не имея ответа...
~~~~~
~lol~~
~~~ Single Password Solution
Re[7]: Есть список чисел, найти одиночек
От: _DAle_ Беларусь  
Дата: 28.04.15 13:45
Оценка:
Здравствуйте, Caracrist, Вы писали:

C>ну мы оба понимаем, что врядли на том ресурсе вопрос задали не имея ответа...


Ну так там же никто и не требует O(n) скорости и O(1) памяти. Да и может не выделываются, и считают k константой.
Re: Есть список чисел, найти одиночек
От: Chorkov Россия  
Дата: 29.04.15 09:25
Оценка: 6 (1)
Здравствуйте, Caracrist, Вы писали:

Еще один родственный баян:

Есть список чисел, в котором все числа встречаются трижды, кроме одного.
Найти это число.
Ограничение: O(1) по памяти, один проход по списку.
Re[2]: Есть список чисел, найти одиночек
От: Кодт Россия  
Дата: 29.04.15 11:24
Оценка:
Здравствуйте, Chorkov, Вы писали:

C>Есть список чисел, в котором все числа встречаются трижды, кроме одного.

C>Найти это число.
C>Ограничение: O(1) по памяти, один проход по списку.

  спойлер: триты
Использовать триты вместо битов.
Можно даже, чтобы не заниматься честным переводом всех чисел в троичную систему, тупо расширить каждый бит до трита, а трит — до двух бит.
Тогда арифметика получится очень простая.

typedef uint32_t binary;
typedef uint64_t ternary;

ternary seed() { return (ternary)0; }

ternary terplus(ternary sum, binary x)
{
  // удобно выбрать коды 00, 01, 11

  // hl   x
  // 00 + 0 = 00
  // 00 + 1 = 01
  // 01 + 0 = 01
  // 01 + 1 = 11
  // 11 + 0 = 11
  // 11 + 1 = 00

  binary h = (binary)(sum >> 32);
  binary l = (binary)(sum);

  binary L = ~(h&l&x) & (h|l|x);
  binary H = l&(h^x);

  return ((ternary)H << 32) | L;
}

binary answer(ternary sum)
{
  binary h = (binary)(sum >> 32);
  binary l = (binary)(sum);

  assert(h == 0);
  return l;
}

template<class SERIES>
binary find_unique(SERIES series)
{
  ternary sum = seed();
  int num = 0;
  for(binary x : series)
  {
    sum = terplus(sum,x);
    num++;
  }
  assert(num % 3 == 1);
  return answer(sum);
}
Перекуём баги на фичи!
Отредактировано 29.04.2015 11:25 Кодт . Предыдущая версия .
Re[2]: Есть список чисел, найти одиночек
От: _DAle_ Беларусь  
Дата: 29.04.15 11:45
Оценка:
Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, Caracrist, Вы писали:


C>Еще один родственный баян:


C>Есть список чисел, в котором все числа встречаются трижды, кроме одного.

C>Найти это число.
C>Ограничение: O(1) по памяти, один проход по списку.

Ну по идее тоже самое, просто вместо побитового сложения по модулю 2 (xor), надо делать поразрядное сложение по модулю три чисел, переведенных в троичную СС.
Отредактировано 29.04.2015 11:46 _DAle_ . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.