How to become an author
Search
Write a publication
Pull to refresh

Comments 38

«В конце мы получаем «наиболее вероятного кандидата» на присутствие в N/2 экземплярах: если такой элемент в массиве действительно существует, то он будет найден; если же такого элемента нет, то возможно, стоять останется просто какой-то бедолага, которому не хватило пары. Для более строгой реализации majority требуется пройти по массиву второй раз и проверить, действительно ли найденный элемент встречается требуемое количество раз.»

Правильно ли я понимаю, что второй проход по массиву нужен только если N — нечетное? А если N — четное, то тогда либо «никого не останется», либо «останутся как минимум 2 представителя большинства».
Total votes 4: ↑3 and ↓1+2
Второй проход требуется, чтобы в ситуации, когда такого элемента в принципе нет (условие задачи «некий элемент встречается как минимум N/2 раз» не выполняется) — понять это, а не выдать неверный ответ
Total votes 2: ↑2 and ↓0+2
Сказал, не подумав.
Здесь важно, что элемент встречается строго больше, чем N/2 раз
иначе все действительно ломается при нечетном N:
N=5
12134
результат — 4
Total votes 2: ↑2 and ↓0+2
Да, думаю, я понял, спасибо, отличный пример. Но у вас N = 5 — нечетное. Я как раз говорил что в этом случае может быть нужна проверка.

Однако, с вашей подачи я придумал другой пример, который опровергает то, что я написал ваше.
Если взять N = 6 и массив [112345] и удалить пары 23 и 45, то остануться элементы 11, которые не являются удовлетворяющими условиям поиска.
Total votes 1: ↑1 and ↓0+1
Нет, я все правильно написал=)
Как раз про Ваш пример.

Еще раз. Для нечетного числа проверка нужна, если в условии будет нестрогое неравенство:
«некий элемент встречается как минимум N/2 раз»

Тогда, действительно, написанное Вами верно, и я лишь привел пример для N=5

Но на самом деле в условии строгое неравенство:
«Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.»

И тут уже при выполнении условия выполнение второго прохода не требуется ни для каких N.

кстати, в вашем примере
112345
алгоритм выдаст 5 (опять же, условие задачи не выполнено)
Total votes 1: ↑1 and ↓0+1
А какая разница сколько проходов? Алгоритмически сложность все равно o(N), а операций даже при одном проходе может быть 10*N, второй проход добавит лишь N.
Кстати во втором случае сложность как я понимаю o(k*N), если k сравнимо c N.
This comment wasn’t rated yet0
Второй проход может оказаться физически невозможным. Например, в ситуации, когда данные поступают в реальном времени, а памяти для их сохранения нет. Но тогда нам должны гарантировать, что есть подходящий элемент.
This comment wasn’t rated yet0
Во втором случае всё равно O(N) — ниже winger уже пояснил, почему.
This comment wasn’t rated yet0
1. А тесты будут ??
2.Не лучше бы использовать Buckets тогда вообще не придется использовать поиск ???
Buckets это хеш таблицы без колизий!!!
Total votes 20: ↑1 and ↓19-18
Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Покажите мне, что ли, такую реализацию Dictionary, которая за O(1) будет позволять достучаться до произвольного элемента.
Total votes 2: ↑1 and ↓10
Любая хэш-таблица даёт в среднем O(1)
Total votes 3: ↑2 and ↓1+1
Тогда следовало заметить, что и предложенный алгоритм с хэш-таблицами в среднем даёт O(N).
Total votes 4: ↑2 and ↓20
А никто с этим не спорит и в статье это указано. Но решение со словарем требует дополнительной памяти O(N), а этот алгоритм нет.
Total votes 1: ↑1 and ↓0+1
Он не «предложенный» — как раз взамен ему предлагается более эффективный.
This comment wasn’t rated yet0
«Предложенный», «упомянутый», «описанный» — один хер, асимптотика всё равно неверная.
Total votes 5: ↑1 and ↓4-3
Может кто знает, можно ли как-нибудь подсчитать кол-во повторений (частоту слов) через regexp?
Total votes 2: ↑0 and ↓2-2
Асимптотика второго алгоритма будет O(N*k) из-за foreach(int l in candidates.Keys).
This comment wasn’t rated yet0
Исходя из смысла задачи, k существенно меньше N, поэтому можно ее считать константой и пренебречь.
This comment wasn’t rated yet0
Вы имеете ввиду проверку candidates.ContainsKey(array[i])?
Но ведь если словарь реализован как самобалансирующееся дерево, то в нем поиск осуществляется за log(n). Т.е. сложность второго алгоритма будет O(N*log(k)). Я думаю, что при относительно малых k, величиной log(k) можно пренебречь.
This comment wasn’t rated yet0
Я имел ввиду
foreach(int l in candidates.Keys) if (candidates[l]-- == 0) candidates.Remove(l);
Правда я только что осознал что амортизированно там будет O(1) декрементов :)
Total votes 3: ↑3 and ↓0+3
Читателям в качестве упражнения предлагается понять, почему строчка (**) не нарушает линейности алгоритма.

Это был намеренный «подвох» :)
Total votes 1: ↑0 and ↓1-1
Возможно, это многим покажется очевидно, но всё же замечу: первый алгоритм обнаруживает числа, которых строго больше половины в исходной последовательности. Для ситуации, когда их может быть ровно половина, такой алгоритм даст сбой на последовательностях вида ACBС, где A, B и C — разные числа (при необходимости повторённых любое количество раз).
Total votes 1: ↑1 and ↓0+1
Собственно, первая строчка статьи это и говорит: "Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз."
Total votes 2: ↑1 and ↓10
Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Заметим, что если отсортировать массив, то искомое число будет находиться на непрерывном отрезке индексов, который будет длинее N/2. Это значит, что какое бы ни было это число — оно обязательно покроет ячейку массива с номером N/2.

Другими словами, надо найти число, которое после сортировки встанет на позицию N/2, а это можно найти вызовом одной функции nth_element в С++.
Total votes 2: ↑2 and ↓0+2
Да, но сортировка — это O(n*log(n)), а тут O(n).
К тому же, не всегда возможна сортировка in-place, а иначе надо дополнительно O(n) памяти.
Т.е. этот алгоритм необходим, когда существуют серьезные ограничения по использованию других, более очевидных, но и несколько более дорогостоящих алгоритмов.
Total votes 1: ↑1 and ↓0+1
Никакой сортировки в решении нет, она есть только в объяснении алгоритма.

int find(vector<int> a) {
	nth_element(a.begin(), a.begin() + (a.size() / 2), a.end());
	return a[a.size() / 2];
}
Total votes 3: ↑2 and ↓1+1
Есть частичная сортировка.
Total votes 1: ↑1 and ↓0+1
Да, согласен. Почему-то на nth_element в первом сообщении вообще внимания не обратил.
This comment wasn’t rated yet0
Да, это верно для элемента, повторяющегося больше N/2 раз, но этот подход невозможно обобщить для N/3 и N/k.
Кроме того, алгоритм nth_element и сложнее в реализации, чем предложенный, и сложнее него вычислительно (рекурсия требует O(log N) дополнительной памяти).
This comment wasn’t rated yet0
А нужна ли в nth_element рекурсия? Если он реализован «за O(N) в среднем», используя идеи быстрой сортировки, то это просто цикл. В честной реализации за гарантированные O(N) без рекурсии обойтись сложно, но писал ли её кто-нибудь когда-нибудь вообще?
This comment wasn’t rated yet0
И, кстати, почему невозможно обобщить? Чтобы вывести правильные элементы в точки N/k, (2*N)/k, ..., (k-1)*N/k, потребуется O(N*log(k)) операций, столько же, сколько для реализации словаря с помощью дерева. Словарь в виде хеш-таблицы, конечно, не догнать.
Total votes 1: ↑1 and ↓0+1
вообще-то я прекрасно знаю, что она делает, я ж сказал
надо найти число, которое после сортировки встанет на позицию N/2
. в следующий раз читайте внимательнее
Total votes 4: ↑1 and ↓3-2
Я это не для вас оставлял а для людей которые на C++ не программируют и с nth_element дело не имеют. Им будет полезна ссылка к теории, чтобы иметь представление о чем идет речь.
This comment wasn’t rated yet0
А ведь ту же идею можно использовать для поиска точки сгущения в облаке. Если нам надо найти шар радиуса R, содержащий больше, чем 1/k точек, то поступаем точно так же, но вместо проверки равенства точек проверяем, что расстояние между ними меньше 2*R (придётся немного повозиться при создании «группы стоящих» — если двое стояли рядом, надо запомнить их обоих, а когда рядом с ними найдётся третий, взять в качестве центра того из двух, кто ближе к третьему. Или середину самой короткой стороны треугольника).
Выглядит гораздо проще других алгоритмов. И за один проход :)
Total votes 1: ↑1 and ↓0+1
В сборнике задач K&R помимо этой была ещё такая задача (к сожалению не могу нагуглить):
На космическом корабле вышли из строя некоторые из N процессоров, при этим исправных осталось больше половины. Процессор можно спросить, исправен ли какой-то другой. Исправный процесс выдаст правильный ответ, неисправный ответит ложью. Как за N/2+1 (или N/2?) таких запросов найти исправный процессор.
Total votes 1: ↑1 and ↓0+1
Слишком поздно, похоже мозги совсем не соображают.
Как быть в случае если первая пара «села», т.к. элементы не совпадают, села также и следующая,
но скажем во второй паре один элемент совпал с одним из первой пары?
This comment wasn’t rated yet0
Это не важно. Главное, что в оставшемся массиве одинаковых элементов всё равно больше половины: в самом худшем случае, когда одинаковые элементы и 1 и 2 пары это и есть искомый элемент, получается, что одинаковых мы вычеркнули столько же, сколько неодинаковых — а значит, условие сохранилось.
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr