Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 38
«В конце мы получаем «наиболее вероятного кандидата» на присутствие в N/2 экземплярах: если такой элемент в массиве действительно существует, то он будет найден; если же такого элемента нет, то возможно, стоять останется просто какой-то бедолага, которому не хватило пары. Для более строгой реализации majority требуется пройти по массиву второй раз и проверить, действительно ли найденный элемент встречается требуемое количество раз.»
Правильно ли я понимаю, что второй проход по массиву нужен только если N — нечетное? А если N — четное, то тогда либо «никого не останется», либо «останутся как минимум 2 представителя большинства».
Правильно ли я понимаю, что второй проход по массиву нужен только если N — нечетное? А если N — четное, то тогда либо «никого не останется», либо «останутся как минимум 2 представителя большинства».
Второй проход требуется, чтобы в ситуации, когда такого элемента в принципе нет (условие задачи «некий элемент встречается как минимум N/2 раз» не выполняется) — понять это, а не выдать неверный ответ
Сказал, не подумав.
Здесь важно, что элемент встречается строго больше, чем N/2 раз
иначе все действительно ломается при нечетном N:
N=5
12134
результат — 4
Здесь важно, что элемент встречается строго больше, чем N/2 раз
иначе все действительно ломается при нечетном N:
N=5
12134
результат — 4
Да, думаю, я понял, спасибо, отличный пример. Но у вас N = 5 — нечетное. Я как раз говорил что в этом случае может быть нужна проверка.
Однако, с вашей подачи я придумал другой пример, который опровергает то, что я написал ваше.
Если взять N = 6 и массив [112345] и удалить пары 23 и 45, то остануться элементы 11, которые не являются удовлетворяющими условиям поиска.
Однако, с вашей подачи я придумал другой пример, который опровергает то, что я написал ваше.
Если взять N = 6 и массив [112345] и удалить пары 23 и 45, то остануться элементы 11, которые не являются удовлетворяющими условиям поиска.
Нет, я все правильно написал=)
Как раз про Ваш пример.
Еще раз. Для нечетного числа проверка нужна, если в условии будет нестрогое неравенство:
«некий элемент встречается как минимум N/2 раз»
Тогда, действительно, написанное Вами верно, и я лишь привел пример для N=5
Но на самом деле в условии строгое неравенство:
«Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.»
И тут уже при выполнении условия выполнение второго прохода не требуется ни для каких N.
кстати, в вашем примере
112345
алгоритм выдаст 5 (опять же, условие задачи не выполнено)
Как раз про Ваш пример.
Еще раз. Для нечетного числа проверка нужна, если в условии будет нестрогое неравенство:
«некий элемент встречается как минимум N/2 раз»
Тогда, действительно, написанное Вами верно, и я лишь привел пример для N=5
Но на самом деле в условии строгое неравенство:
«Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.»
И тут уже при выполнении условия выполнение второго прохода не требуется ни для каких N.
кстати, в вашем примере
112345
алгоритм выдаст 5 (опять же, условие задачи не выполнено)
А какая разница сколько проходов? Алгоритмически сложность все равно o(N), а операций даже при одном проходе может быть 10*N, второй проход добавит лишь N.
Кстати во втором случае сложность как я понимаю o(k*N), если k сравнимо c N.
Кстати во втором случае сложность как я понимаю o(k*N), если k сравнимо c N.
Второй проход может оказаться физически невозможным. Например, в ситуации, когда данные поступают в реальном времени, а памяти для их сохранения нет. Но тогда нам должны гарантировать, что есть подходящий элемент.
Во втором случае всё равно O(N) — ниже winger уже пояснил, почему.
1. А тесты будут ??
2.Не лучше бы использовать Buckets тогда вообще не придется использовать поиск ???
Buckets это хеш таблицы без колизий!!!
2.Не лучше бы использовать Buckets тогда вообще не придется использовать поиск ???
Buckets это хеш таблицы без колизий!!!
Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?
Покажите мне, что ли, такую реализацию Dictionary, которая за O(1) будет позволять достучаться до произвольного элемента.
Может кто знает, можно ли как-нибудь подсчитать кол-во повторений (частоту слов) через regexp?
Асимптотика второго алгоритма будет O(N*k) из-за foreach(int l in candidates.Keys).
Исходя из смысла задачи, k существенно меньше N, поэтому можно ее считать константой и пренебречь.
Вы имеете ввиду проверку candidates.ContainsKey(array[i])?
Но ведь если словарь реализован как самобалансирующееся дерево, то в нем поиск осуществляется за log(n). Т.е. сложность второго алгоритма будет O(N*log(k)). Я думаю, что при относительно малых k, величиной log(k) можно пренебречь.
Но ведь если словарь реализован как самобалансирующееся дерево, то в нем поиск осуществляется за log(n). Т.е. сложность второго алгоритма будет O(N*log(k)). Я думаю, что при относительно малых k, величиной log(k) можно пренебречь.
Читателям в качестве упражнения предлагается понять, почему строчка (**) не нарушает линейности алгоритма.
Это был намеренный «подвох» :)
Возможно, это многим покажется очевидно, но всё же замечу: первый алгоритм обнаруживает числа, которых строго больше половины в исходной последовательности. Для ситуации, когда их может быть ровно половина, такой алгоритм даст сбой на последовательностях вида ACBС, где A, B и C — разные числа (при необходимости повторённых любое количество раз).
Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.
Заметим, что если отсортировать массив, то искомое число будет находиться на непрерывном отрезке индексов, который будет длинее N/2. Это значит, что какое бы ни было это число — оно обязательно покроет ячейку массива с номером N/2.
Другими словами, надо найти число, которое после сортировки встанет на позицию N/2, а это можно найти вызовом одной функции nth_element в С++.
Заметим, что если отсортировать массив, то искомое число будет находиться на непрерывном отрезке индексов, который будет длинее N/2. Это значит, что какое бы ни было это число — оно обязательно покроет ячейку массива с номером N/2.
Другими словами, надо найти число, которое после сортировки встанет на позицию N/2, а это можно найти вызовом одной функции nth_element в С++.
Да, но сортировка — это O(n*log(n)), а тут O(n).
К тому же, не всегда возможна сортировка in-place, а иначе надо дополнительно O(n) памяти.
Т.е. этот алгоритм необходим, когда существуют серьезные ограничения по использованию других, более очевидных, но и несколько более дорогостоящих алгоритмов.
К тому же, не всегда возможна сортировка in-place, а иначе надо дополнительно O(n) памяти.
Т.е. этот алгоритм необходим, когда существуют серьезные ограничения по использованию других, более очевидных, но и несколько более дорогостоящих алгоритмов.
Да, это верно для элемента, повторяющегося больше N/2 раз, но этот подход невозможно обобщить для N/3 и N/k.
Кроме того, алгоритм
Кроме того, алгоритм
nth_element и сложнее в реализации, чем предложенный, и сложнее него вычислительно (рекурсия требует O(log N) дополнительной памяти).А нужна ли в nth_element рекурсия? Если он реализован «за O(N) в среднем», используя идеи быстрой сортировки, то это просто цикл. В честной реализации за гарантированные O(N) без рекурсии обойтись сложно, но писал ли её кто-нибудь когда-нибудь вообще?
И, кстати, почему невозможно обобщить? Чтобы вывести правильные элементы в точки N/k, (2*N)/k, ..., (k-1)*N/k, потребуется O(N*log(k)) операций, столько же, сколько для реализации словаря с помощью дерева. Словарь в виде хеш-таблицы, конечно, не догнать.
A nth_element есть ничто иное как Selection Algorithm или K-тая порядковая статистика.
А ведь ту же идею можно использовать для поиска точки сгущения в облаке. Если нам надо найти шар радиуса R, содержащий больше, чем 1/k точек, то поступаем точно так же, но вместо проверки равенства точек проверяем, что расстояние между ними меньше 2*R (придётся немного повозиться при создании «группы стоящих» — если двое стояли рядом, надо запомнить их обоих, а когда рядом с ними найдётся третий, взять в качестве центра того из двух, кто ближе к третьему. Или середину самой короткой стороны треугольника).
Выглядит гораздо проще других алгоритмов. И за один проход :)
Выглядит гораздо проще других алгоритмов. И за один проход :)
В сборнике задач K&R помимо этой была ещё такая задача (к сожалению не могу нагуглить):
На космическом корабле вышли из строя некоторые из N процессоров, при этим исправных осталось больше половины. Процессор можно спросить, исправен ли какой-то другой. Исправный процесс выдаст правильный ответ, неисправный ответит ложью. Как за N/2+1 (или N/2?) таких запросов найти исправный процессор.
На космическом корабле вышли из строя некоторые из N процессоров, при этим исправных осталось больше половины. Процессор можно спросить, исправен ли какой-то другой. Исправный процесс выдаст правильный ответ, неисправный ответит ложью. Как за N/2+1 (или N/2?) таких запросов найти исправный процессор.
Слишком поздно, похоже мозги совсем не соображают.
Как быть в случае если первая пара «села», т.к. элементы не совпадают, села также и следующая,
но скажем во второй паре один элемент совпал с одним из первой пары?
Как быть в случае если первая пара «села», т.к. элементы не совпадают, села также и следующая,
но скажем во второй паре один элемент совпал с одним из первой пары?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск часто встречающихся элементов в массиве