Найдите наибольшие 10% чисел в массиве, чтобы

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

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

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

Algo-1

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

Algo-2

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

Algo-3

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

Ответ 1

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

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

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

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

Ответ 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, использовать следующую процедуру быстрой сортировки.

Выберите точку опоры
Сканируйте все элементы и поместите их в один из двух ведер: те, которые меньше, чем свод (левое ведро), и те, которые больше, чем сравнения (правое ведро) (n-1). Следуйте процедуре быстрой сортировки обмена на месте.
а. Размер ведра справа == n/10: Вы закончили.

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

с. Размер ковша справа < n/10, то новый список - ведро слева, но вы хотите найти самый большой n-n/10- (размер правого ведра). Рекурсивно перейдите к шагу 1 с новым списком.

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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

Ответ 8

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

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