Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
Плохо только то, что максимальное число попыток теоретически не ограничено. В очень редком случае рандом может выпадать так, что цикл будет продолжаться бесконечно. )
Так что интересно было бы увидеть решение O(1) без рандома. Рандом, кстати, несколько затратный по ресурсам. Это, конечно, константа, но...
Кстати, из тех же самых соображений о минимальном числе попыток, ваш самый первый метод с хэшем по идее превращается в такой же константный и интуитивно думаю, что даже с меньшим числом попыток, ведь мы сравниваем очередное число не с одним, а со всеми числами, которые на данный момент есть в словаре.
Если массив был случайно перемешан, да. Однако, если нам назло подсунули плохой массив, будет O(n), например:
[1, 2, 3, ..., 1000, 1, 1, 1, ..., 1]Решение за O(1) по памяти без рандома здесь: https://youtu.be/B-1h5xEjBvk?si=RVxUnYKOJnnx-wZK&t=791
Видео не хотелось бы смотреть ) Почему бы в тексте это решение не показать? ) Но, повторюсь, по факту решение с set и есть O(1), если не брать совсем уж злонамеренные данные.
Авторы видео ошиблись решение не за O(1), а за O(n), так как в итоге они итерируются по всей длине массива. А так как это вложенный цикл, то они в итоге это делают 3 раза.
В итоге я погонял тесты. Интуиция меня всё-таки обманула:
метод с
randomи метод сsetпрактически одинаковые по скорости работысреднее число попыток у них одинаковое: 4
при этом у
randomбольше разброс количества попыток и (что логично из этого вытекает) почти в 2 раза больше максимальное число попыток, которое понадобилось
Таким образом, вполне можно считать, что метод с set тоже O(1) и по скорости и по памяти, и при этом он стабильнее, чем метод с random (меньше разброс требуемых попыток, а значит и времени работы метода).
P.S. Конечно, если подавать злонамеренно подготовленные данные, то метод с random предпочтительнее. Метод с set, если ему злонамеренно ставить в конец повторяющееся число, будет всегда перебирать половину массива. Конечно, можно перебирать тогда специально в обратном порядке, но тогда можно ставить эти числа в середину, и перебираться всё-равно будет четверть массива, хоть по порядку перебирай, хоть обратно. Но если злонамеренность не ожидается, то метод с set предпочтительнее.
Если массив на вход подается случайный, то метод random ничего нового не привносит. Разумеется, он только замедлит. Однако, на плохих входах будет деградация до O(N).
Можно совместить set и random. Обход массива сделать со случайного выбранного элемента и случайно выбранным шагом:
step = random() % 2n;
i = random() % 2n;
for(j = 0; j < 2n; j++) {
i = (i + step) % 2n;
... проверка array[i]
}
Тьфу, блин, я неправильно считал. Я считал число итераций цикла. И в случае с set будет 4 шага по циклу, но на первом то шаге мы ничего не сравниваем, сравнения начинаются со второго шага. Значит, интуиция меня всё-таки не обманула - в варианте с set достаточно в среднем 3-х проверок, как я и предполагал. ) Что меньше, чем 4 для random варианта.
Кстати, для массивов маленького размера возможно list даже будет быстрее, чем set.
Сортировка пузырьком до первого совпадения двух соседних элементов. Думаю большинство случаев будут решены еще до завершения первого прохода, и дополнительной памяти не надо.
Использовать рандом в таких задачах плохой тон, т.к. в общем случае алгоритм может зацикливаться, при этом есть простые алгоритмы гарантированно находящие решение за O(n).
Например, если понадобится модифицировать условие так что число повторяется не n раз а 2, и количество элементов будет например 10 миллионов, алгоритм с рандомом перестанет работать за вменяемое время.
Можно последовательно рассматривать тройки чисел: сначала попарно сравнивать первые 3 числа (arr[0], arr[1], arr[2]), потом (arr[3], arr[4], arr[5]), и т.д. Рано или поздно придем к такой тройке (или остаточной двойке чисел), где есть два одинаковых элемента
Это не сработает, если длина массива меньше 6, но частный кейс не проблема. Зато вариант будет работать, даже если искомое число встречается не в половине элементов массива, а чуть более чем в трети.
Да, именно так :)
Решение авторов именно такое.
Толково. Добавил к моим тестам, по времени получается примерно как другие два метода, при этом в среднем тут достаточно двух шагов алгоритма, чтобы найти число.
Есть другой вариант: рассмотрите каждую из n/2 соседних пар. Если нашли совпадение - это ответ. если не нашли, то у нас эти n повторяющихся элементов разбиты по n парам, по одной в каждой. Значит среди, первых (или последних) четырех точно есть повторение. Так что надо сравнить arr[0] с arr[2] и arr[3]. Если совпало - вы нашли число arr[0]. Если нет, то искомое число arr[1].
Тут нет частных случаев, работает даже для n=4. Для n=2 задача не имеет смысла, ибо "повторяющееся" число там повторяется один раз и никак не отличимо от уникального числа.
А вот интересный вопрос: как решать усложненную задачу, где одно число встречается ровно N/2 раз, а все остальные меньше и они могут повторятся? Отличие от изначальной задачи, что вспомогательные редкие числа уже не уникальны и нельзя любую пару совпадающих чисел считать ответом. Но все-равно только одно число самое частое и встречается N/2 раз.
Тут ясно, как делать с сортировкой или hash-map-ами. Но за O(N) по времени и O(1) памяти это как сделать?
Чуть более простую задачу, где ровно одно число встречается строго больше N/2 раз, известно, как решать - там надо "аннигилировать" различные элементы парочками. Поддерживаем инвариант, что у нас среди рассмотренных чисел уничтожены все, кроме скольких-то копий одного числа. При добавлении нового числа в рассмотрение оно или аннигилирует с существующим или добавляется к ответу. Последнее не уничтоженное число - это и будет ответ:
int current = 0;
int cnt = 0;
for (int x : arr) {
if (x == current) {
++cnt;
} else {
if (cnt == 0) {
cnt = 1;
current = x;
} else {
--cnt;
}
}
}
return current;Это работает, потому что даже если вы уничтожаете в каждой парочке искомое число, вы все его копии не уничтожите, ибо их больше N/2, а аннигиляций будет не больше N/2. Если же вы какие-то левые элементы вместе уничтожите, то тем более искомое число останется в конце.
Но вот если у вас ровно N/2 самого частого числа, а всех остальных строго меньше, то это уже не сработает. Можно нечаянно уничтожить все копии искомого. Тут мне видится одно решение: если в конце осталось что-то, то это ответ. Если же в конце осталось 0 чисел, то мы во всех парочках аннигилировали искомое число с чем-то еще. Теоретически, можно просто отслеживать, какие числа мы аннигилировали и запоминать те одно-два, которые встречались во всех аннигилирующих парах. С каждой новой аннигиляцией вычеркнуть те, что не повторились. В конце должно остаться ровно одно число
Есть ли у кого-нибудь идеи попроще?
Аннигилировать тройки. Это обобщение упомянутого Бойера-Мура, я как-то уже писал
Останутся 2 кандидата, далее проверка одного из них.
Не уверен, что это проще, но зато работает и на меньшем количестве искомого числа.
А если говорить про вашу идею с аннигиляцией пар, то в ситуации, когда осталось 0 чисел, у нас так же есть два кандидата - самая первая уничтоженная пара. Проверяем одно число из этой пары.
Проверяем одно число из этой пары.
Спасибо, концептуально это проще, да. Можно даже не делать потом отдельный проход по массиву для счета их вхождений, а сразу вместе с вычеркиванием считать для двух фиксированных чисел в первой паре.
Аннигилировать тройки
А вот тут не понял, как это должно работать? Типа нашли 2 числа, каждое из которых встречается больше n/3 раз и потом их оба проверить на количество вхождений n/2?
Хорошая задача, она демонстрирует основной результат теории, которую называют красивым словом "heavy hitters theory" (не знаю, как правильно перевести на русский - может, "важные чуваки"?)
Лет 10 назад она активно развивалась, и было много научных работ на эту тему (последнее время я за ней не слежу, может, до сих пор там что-то новое придумывают)
Там два основных результата - это теорема Бойера-Мура о поиске значений, встречающихся в потоке больше половины раз , о которой @Alexandroppolus упоминает, и ее обобщение на n/k раз теорема Мисра-Грис.
Также там активно исследовались вероятностные методы, так что идея автора (если я правильно понимаю) - очень хорошая на практике, потому что вероятность ложного результата обычно падает экспоненциально по количеству попыток. То есть, если взять ваш алгоритм и повторить раз 50, то вероятность его ошибки будет сильно меньше вероятности того, что прилетит заряженная частица с солнца и поменяет бит в памяти компьютера. Конечно, есть еще вероятность злонамеренной атаки на генератор случайных чисел, но эта проблема тоже имеет теоретическое решение :)
Ну и важная часть исследований доказывает разные ограничения. Я знаю реальный случай, когда начальник попросил программиста найти моду (самое повторяющееся значение в потоке) с использованием констатной памяти. Программист ему гордо показал теорему, которая говорит, что это невозможно!
Фу, что за фигня. Мы точно решаем или неточно. Есть разница между четкими и приблизительными ответами. Как четкие и нечёткие множества. Короче зависит от тестовых данных. Рандом вообще не причем тут, они ведь уже перемешаны по условию, можно линейно читать считая что рандомно уже применил индекс.
И если решать четко и без памяти особой. То я бы хранил хеш переменную с типом чисел, и xor на каждом шаге с ней текущего, и наверно проверяя с хешем на предыдущем шаге тоже через xor и что-то там смотреть на 0 или не 0 значит нашли. Будет n/2 в худшем итого o(n) как ни крути.
А так, да, если нечеткость решения норм, то можно в зависимости от степени нечеткости Альфа от 0 до 1 выбрать такое k = f(a, n) и потом брать случайно k чисел и также их перебирать, будет просто степень ответа нечеткая.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Константа во всем: одна простая задача за O(1)