Отправлено Andy-spb 13 ноября 2006 г. 15:36

Вроде как на собеседовании кому-то задали..

есть массив N чисел, допустим int. Из них все числа встречаются по два раза, кроме одной пары чисел. Требуется найти эти два числа.

• Ответ: Не совсем такое условие на самом деле: все числа парами, одно без пары. Найти его. Решение - пропустить все через XOR, оно и останется. — radist   (13.11.2006 17:20 217.114.1.6, пустое)
• Если диапазон чисел ограничен: обнулить память, при встрече числа величивать значение в ячейке N на единицу. — Lucky   (13.11.2006 16:53 217.69.212.124, пустое)
• решение без затрат памяти - два вложенных цикла - сравнение каждого с каждым. дальше надо память юзать. что-то мне подсказывает, что нужен будет массив размером в N. — 507   (13.11.2006 16:21 212.176.124.149, пустое)
  • Не каждого с каждым, а на два элемента меньше в каждом цикле итерации(-) — misyachniy   (13.11.2006 17:18 83.218.237.86, пустое)
    • На один ;) — miv   (14.11.2006 10:52 82.140.84.195, пустое)
• Что-то мне подсказывает что здесь должно сыграть XOR... — ETM   (13.11.2006 16:07 62.117.85.87, пустое)
  • Скорее 3 ортогональных последовательности "+" и "-" — argus98   (13.11.2006 16:16 81.22.205.230, пустое)
    • поясните плиз. — Andy-spb   (13.11.2006 16:28 83.149.3.166, пустое)
      • Берем сначала сумму всех элементов (+): — argus98   (13.11.2006 16:46 81.22.205.230, 510 байт)
  • Контольная сумма по "xor" исходного массива - будет "xor" искомых элементов.. Дальше пока не придумал... — ETM   (13.11.2006 16:16 62.117.85.87, пустое)
    • +1 :-) — Andy-spb   (13.11.2006 16:26 83.149.3.166, пустое)
  • если требуется ыделть одно число,т такая адачка кк раз и решается с помощью XORэлеменарн !от а зо ив — Andy-spb   (13.11.2006 16:12 83.149.3.166, пустое)
• Давно когда-то решали задачу поиска наиболее часто встречающегося значения, но ссылку убрали в архив.(+) => — quark   (13.11.2006 16:05 62.140.241.223, 1152 байт, ссылка)
  • Типа того: — quark   (13.11.2006 17:03 62.140.241.223, 563 байт)
• первое что на ум пришло - рекурсия, памяти только съест немеряно — IV   (13.11.2006 16:03 81.23.109.150, пустое)
• условия решения есть? а так она в лоб элементарно решается — ы   (13.11.2006 15:40 80.92.98.211, пустое)
  • условия как обычно - максимально эффективно по памяти или по скорости. — Andy-spb   (13.11.2006 15:44 83.149.3.166, пустое)
• Может отсортировать сначала? Есть миллион обсосанных алгоритмов — Крок   (13.11.2006 15:40 91.76.32.20, пустое)
  • сортировка съест время и память и толком ничего не даст :) — Andy-spb   (13.11.2006 15:48 83.149.3.166, 126 байт)
    • И память не съёст ))) — Крок   (13.11.2006 16:01 91.76.32.20, пустое)