Найдите самые большие 10% чисел в массиве по порядку

Question

Учитывая массив с 'N' числами (N> 100). Как мы можем найти самые большие 10% из них по порядку? (если n / 10 не является целым числом, мы можем округлить его)

Я придумал 3 алгоритма, чтобы попытаться решить вышеуказанную проблему, но я не уверен, какой из них является лучшим с точки зрения асимптотического времени выполнения. Могу ли я на самом деле внести какие-либо изменения, чтобы уменьшить асимптотическое время? Кроме того, если N становится действительно большим, какой алгоритм все еще может быть эффективным?

Я перечисляю свои идеи для приведенных ниже алгоритмов и мог бы действительно помочь найти наиболее эффективный алгоритм для этого.

Algo-1

Я использовал сортировку выбора и остановил ее после сортировки 10% чисел.

Algo-2

Я построил максимальную кучу и продолжал удалять самые большие 10% чисел

Algo-3

Я не реализовал это, но у меня есть идея использовать любой алгоритм статистики заказов, чтобы найти раздел, содержащий первые 10% чисел, а затем отсортировать их с помощью сортировки слиянием.

Answer 1

Самое быстрое решение - использовать алгоритм выбора на основе разделов , который работает в O(n). Он основан на идее быстрой сортировки, за исключением того, что вместо рекурсивной сортировки обоих разделов вы переходите только к одному из разделов, чтобы найти самый маленький элемент k-th.

Нахождение наибольшего 10% достигается путем поиска k=(90%*N)-th наименьшего числа.

Если вы помните, как работает разбиение в быстрой сортировке, элементы, меньшие, чем стержень, перемещаются влево, а остальные элементы - вправо. Допустим, вы хотите выбрать самый маленький элемент k-th. Затем вы увидите, есть ли хотя бы k элементов слева от оси. Если есть, то вы знаете, что можете игнорировать элементы в правильном разделе. В противном случае вы можете игнорировать все элементы в левом разделе, потому что вы знаете, что этот элемент будет в правом разделе.

Обратите внимание, что алгоритм выбора определяет только те верхние 10% чисел. Если вам нужно, чтобы они были отсортированы, то вам нужно отсортировать эти числа (но только эти числа, остальные 90% можно игнорировать).

Answer 2

Algo-1: Сортировка выбора будет выполняться в O (n ^ 2). Первое сканирование, которое вы делаете (n-1), сравнивает, второе время (n-2), время n / 10 (nn / 10), поэтому (n-1) + (n-2) + ... + (nn / 10) => O (n ^ 2)

Algo-2: Удаление элемента max из кучи - O (log n), так что этот будет запускаться O (n log n), так как вы хотите удалить n / 10 элементов.

Еще один возможный алгоритм, хотя все еще O (n log n), но я думаю, что может быть лучше, чем Algo-2, - это использовать следующую процедуру быстрой сортировки.

1. Укажите опорную точку
2. Отсканируйте все элементы и поместите их в одно из двух сегментов: те, которые меньше, чем сравнение по центру (левый сегмент), и те, которые больше, чем сравнение по центру (правый сегмент) (n-1). Выполните процедуру быстрой сортировки обмена на месте.

3. а. Размер ведра справа == н / 10: все готово.

   б. Размер сегмента справа> n / 10, тогда новый список соответствует сегменту справа, рекурсивно перейдите к шагу 1 с новым списком.

   с. Размер сегмента справа

Answer 3

Создайте кучу с O (lnN) стоимостью замены, заполненной первыми n / 10 элементами. Отсканируйте оставшиеся числа, сравнивая их с наименьшим значением в куче. Если значение текущего элемента выше, чем наименьший элемент в куче, вставьте его в кучу и удалите наименьший элемент. В худшем случае две операции сканирования O (lnN), умноженные на N, дают O (N ln N), что не лучше по времени, чем сортировка, но требует меньше памяти, чем сортировка всего, так как на практике это может быть быстрее (особенно если N элементов не помещаются в кэш, но n / 10 будет соответствовать - асимптотическое время имеет значение только для того, кто находится в плоском пространстве).

Answer 4

Я бы использовал быструю сортировку по убыванию в массиве и получил бы первые N / 10 элементов.

Answer 5

, потому что это домашнее задание, мой ответ будет любой алгоритм сортировки, это потому, что вы не можете решить эту проблему в O (n * log (n)).

если бы это было возможно, тогда вы могли бы полностью отсортировать массив в O (n * log (n)). (найдя отсортированные верхние 10% в массиве, который вы хотите полностью отсортировать, удалив их и повторив этот процесс 10 раз).

потому что сортировка невозможна при O (n * log (n)), поэтому проблема такова.

Answer 6

Очень глупый вопрос, просто рассортируйте его любым алгоритмом сортировки и возьмите первые N / 10 элементов.

Algo-2 эквивалентно выполнению этого с сортировкой кучи

Answer 7

Наиболее эффективным алгоритмом было бы использование модифицированной быстрой сортировки.

Быстрая сортировка начинается с выбора «среднего» значения и размещения всех значений ниже этого значения слева, а всех большего значения справа. Обычно вы должны идти вниз и рекурсивно сортировать обе стороны, но вам нужно отсортировать только правую сторону, если слева осталось менее 10% элементов.

Если их больше 10%, вам нужно отсортировать только левую сторону и, возможно, только часть левой стороны.

Это не уменьшит сложность ниже оптимального O (N lg N), но уменьшит постоянный коэффициент и сделает его быстрее, чем очевидная «быстрая сортировка, затем выберите первый 10» подход.

Answer 8

Если вы знаете N, просто создайте массив длиной 1/10 от этого. начальное значение для каждой ячейки - Int.MinValue. Изучите каждое число в массиве. Если оно больше наименьшего числа в массиве из десяти процентов, добавьте его.

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