Нахождение максимального числа в массиве

Question

Существует массив чисел, этот массив является нерегулярным, и мы должны найти максимальное число (n), что по крайней мере n число больше, чем это (это число может быть в массиве и может не быть в массиве)

, например, если мы даем 2 5 7 6 9 номер 4 максимальное число, которое по меньшей мере, 4 число (или больше, чем она) больше, чем 4 (5 6 7 9 крупнее)

я решить эту проблему, но я думаю, что она дает ограничение по времени в большом массиве чисел, поэтому я хочу решить эту проблему по-другому , поэтому я использую сортировку слияния для сортировки, потому что она принимает nlog (n), а затем я использую counte r и он рассчитывается от 1 до k, если число k больше, чем k, мы подсчитываем снова, например, мы рассчитываем от 1 до 4, а затем в 5 мы не имеем 5 чисел больше 5, поэтому дадим k-1 = 4, и это является нашим n.

Это хорошо, или может быть, ограничение времени? есть ли у кого-нибудь другая идея?

благодаря

Answer 1

В c++ есть функция называется std::nth_element и он может найти п-й элемент массива в линейное время. Используя эту функцию, вы должны найти N - n-й элемент (где N - общее количество элементов в массиве) и вычесть 1 из него.

Поскольку вы ищете решение в C, вы не можете использовать эту функцию, но вы можете реализовать свое решение аналогичным образом. nth_element выполняет что-то очень похожее на qsort, но он выполняет только раздел на части массива, где находится n-й элемент.

Теперь предположим, что у вас есть nth_element. Мы будем выполнять что-то вроде комбинации бинарного поиска и nth_element. Сначала мы предполагаем, что ответ вопроса - это средний элемент массива (т. Е. N/2-й элемент). Мы используем nth_element, и мы находим N/2-й элемент. Если это больше, чем N/2, мы знаем, что ответ на вашу проблему составляет не менее N/2, в противном случае это будет меньше. В любом случае, чтобы найти ответ, мы продолжим только один из двух разделов, созданных элементом N/2. Если этот раздел является правильным (элементы больше N/2), мы продолжаем решать ту же проблему, в противном случае мы начнем поиск максимального элемента M слева от элемента N/2, который содержит не менее x таких элементов, что x + N/2 > M. Две подзадачи будут иметь одинаковую сложность. Вы продолжаете выполнять эту операцию до тех пор, пока интересующий вас интервал не будет иметь длину 1.

Теперь давайте докажем, что сложность вышеуказанного алгоритма является линейной. Сначала nth_element выполняет линейные операции порядка N, второй nth_element, который считает, что только половина массива будет выполнять операции порядка N/2, третье - в порядке N/4 и так далее. Всего вы выполните операции порядка N + N/2 + N/4 + ... + 1. Эта сумма меньше 2 * N, поэтому ваша сложность по-прежнему линейна.

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

Answer 2

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

Причина в том, что вы хотите отсортировать как можно меньше элементов.

Таким образом, я бы использовал qsort в качестве базового алгоритма и позволял элементу управления управлять разделом для сортировки (вам нужно будет только отсортировать его).