Поиск отсутствующего элемента в массиве

да все я описал, сказав, что числа левые. Это могут быть хеши, а могут... ошметки видеофильмов. Первый байт он конечно востребованный, но где взять байты с кучей лидирующих нулей??? Т.е. 0000 0000 0000 0001, затем 0000 0000 0000 00002 и так далее? Похоже на UTF64 =)))

Идея генерить случайное число и сравнивать тоже интересная...

 

короче, сделал так, что сначала идет массивчик 256 элементов, если облом то 1024, потом 4096, потом 16К =))) 256 действительно иногда обламывается на некоторых данных, но остальные рогатки не дають врагу шанса... Один массивчик - один проход - это быстрее полной сортировки.

 

persicum
учтите, что исходные данные у вас будут в обычной памяти, а вот поле скорей всего не будет вылазить из кэша. зачем вам аж 4 раза перечитывать память, которая на порядок меденнее кэша? что выиграть пытаетесь? ведь вам в любом случае придется считать каждый элемент во входном массиве.

 

А теперь рассмотрим, что среди этих чисел от 0 до 9, не хватает, скажем, восьмёрки.
45 мы посчитали, найдя 0 и 9: 9×(9+1)/2 = 45. Сложив же весь массив, имеем 37. Вычитая 37 из 45, имеем 8.
Но, да — у нас нет 37 и 45, а есть только 7 и 5. Вычитаем 7 из 5, выходит –2.
Однако, учитывая, что числа у нас беззнаковые, и, по правилам машинной арифметики, «заворачиваются» при переполнении, получаем 100 – 2 = 98. Как обычно, выкидываем 9. Так или иначе, остаётся 8.

Магия! =)

 

странно. то не было поста. то появился. чудеса. дубликат убран

 

Лан, забабахал массивчик чуть побольше и оставил один проход. В реальной практике он почти пустой. Где взять подряд стока малых чисел среди 64-битного хлама если только не вводить их преднамеренно?

Это шаманизм... Вот если бы все числа переXORить, тогда волшебство...

 

Если битовая маска не лезет можно цифры группами считать.
Например массив: первая ячейка это цифры от 0-511, вторая 512-1024...
т.е. первый поход находим в каком диапазоне не достаёт числа, второй находим само число.

Или половинки от чисел посчитать, а по ним потом решить что на втором проходе искать.. (такой способ наверное даже к повторам устойчив)
Хотя тут и похитрее мысли есть, но их надо немного обдумать..

 

но это так, к слову: думаю, если родится какая-нибудь действительно революционная идея, автор добавит её в свой алгоритм =)

и, кстати, qqwe прав.
надо бы конкретизировать распределение величин.
проще говоря, каковы типичные значения: (1) длины массива; (2) разности минимального и максимального элементов?

 

Условия задачи яснее ясного - число состояний элемента массива много больше размера массива. То есть в массиве полным полно дыр. Ранее задача решалась методом полной сортировки, что требует несколько десятков проходов. Это показалось расточительным и начался поиск однопроходного решения.

Отчасти был правПульсар1257, когда предложил генерить случайное число и с большой вероятностью этот элемент не будет представлен в массиве, то есть достаточно одного-два прохода. Однако нужно помнить, что изза эффекта дней рождения коллизии будут встречаться гораздо раньше.

революционное решение тоже было найдено - превратить алгоритм битовых зарубок из детерминированного в вероятностный и таким образом искать в неупорядоченном случайном массиве. Какова вероятность что в случайных данных представлены непременно все числа скажем от 0 до 1024? Тут и без распределения Пуассона ясно, что ноль на массу. Поэтому ценой очень скромной памяти задача почти наверняка решается в один проход.

 

Если в массиве N целых чисел (неважно какой разрядности), то хотя бы одно число из интервала 0...N включительно будет в этом массиве отсутствовать. Потому что в этом интервале содержится ровно N+1 число. То есть достаточно битовой маски из N+1 бита, что уже вполне приемлемо. И задача решается за один проход по массиву и один проход по получившейся битовой маске.

 

Atlantic
Спасибо за точное гарантированное решение задачи.
Я и сам частенько употреблял метод голубиных задниц
http://en.wikipedia.org/wiki/Pigeonhole_principle
Но тут испугался элементов массива большой разрядности...

Вместе с тем, как это бывает для вероятностных алгоритмов, они с вероятностью лишь пренебрежимо меньшей полной единицы дают решение гораздо быстрее. Поэтому для числа элементов скажем миллион на практике достаточно 500 зарубок, что предпочтительнее 1000001 зарубки которые нужно периодически обнулять, хотя последнее и дает гарантированный результат.