Как найти k-й по величине элемент в несортированном массиве длины n в O (n)?

220

Я считаю, что есть способ найти k-й по величине элемент в несортированном массиве длины n в O (n). Или, возможно, это «ожидаемый» O (N) или что-то. Как мы можем это сделать?

MrDatabase
источник
49
Кстати, почти каждый алгоритм, описанный здесь, превращается в O (n ^ 2) или O (n log n), когда k == n. То есть я не думаю, что один из них является O (n) для всех значений k. Меня унизили за указание на это, но я подумал, что вы все равно должны знать.
Кирк Штраузер
19
Алгоритмы выбора могут быть O (n) для любого фиксированного значения k. То есть вы можете иметь алгоритм выбора для k = 25, который равен O (n) для любого значения n, и вы можете сделать это для любого конкретного значения k, которое не связано с n. Случай, когда в алгоритме больше нет O (n), - это когда значение k имеет некоторую зависимость от значения n, например, k = n или k = n / 2. Это, однако, не означает, что если вам случится запустить алгоритм k = 25 в списке из 25 элементов, то он внезапно перестанет быть O (n), потому что нотация O описывает свойство алгоритма, а не конкретное запустить его.
Тайлер МакГенри
1
Мне задали этот вопрос в интервью амазонки как общий случай нахождения второго по величине элемента. Кстати, интервьюер вел интервью, я не спрашивал, смогу ли я уничтожить исходный массив (т.е. отсортировать его), поэтому я нашел сложное решение.
Самбатён
4
Это вопрос 9 в колонке 11 («Сортировка») «Программирование жемчуга» Джона Бентли.
Цян Сюй
3
@KirkStrauser: если k == n или k == n-1, то это становится тривиальным. Мы можем получить максимум или второй максимум за один проход. Таким образом, представленные здесь алгоритмы будут практически использоваться для значений k, которые не принадлежат {1,2, n-1, n}
Адитья Джоши

Ответы:

173

Это называется нахождением статистики k-го порядка . Существует очень простой рандомизированный алгоритм (называемый быстрой выборкой ), который принимает O(n)среднее время, время O(n^2)наихудшего случая, и довольно сложный нерандомизированный алгоритм (называемый интроселекцией ), который принимает время O(n)наихудшего случая. В Википедии есть информация , но она не очень хорошая.

Все, что вам нужно, находится на слайдах PowerPoint . Просто чтобы извлечь основной алгоритм алгоритма O(n)наихудшего случая (интроселект):

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

Это также очень подробно описано в книге «Введение в алгоритмы» Cormen et al.

eladv
источник
6
Спасибо за слайды.
Кшитий Банерджи
5
Почему он должен работать в размере 5? Почему он не может работать с размером 3?
Джоффри Баратеон
11
@eladv Ссылка на слайды не работает :(
Миша Морошко
7
@eladv Пожалуйста, исправьте неработающую ссылку.
maxx777
1
@ МишаМорошко ссылка исправлена
alfasin
118

Если вам нужен настоящий O(n)алгоритм, а не O(kn)что-то в этом роде, то вам следует использовать быстрый выбор (в основном это быстрая сортировка, когда вы выбрасываете раздел, который вам не интересен). У моего профессора отличная рецензия с анализом времени выполнения: ( ссылка )

Алгоритм QuickSelect быстро находит k-й наименьший элемент из несортированного массива nэлементов. Это рандомизированный алгоритм , поэтому мы рассчитываем ожидаемое время выполнения в худшем случае .

Вот алгоритм.

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

Каково время работы этого алгоритма? Если противник подбрасывает нам монеты, мы можем обнаружить, что пивот всегда самый большой элемент и kвсегда равен 1, что дает время пробега

T(n) = Theta(n) + T(n-1) = Theta(n2)

Но если выбор действительно случайный, ожидаемое время работы определяется

T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))

где мы делаем не совсем разумное предположение, что рекурсия всегда попадает в большее из A1или A2.

Давайте догадаемся, что T(n) <= anдля некоторых a. Тогда мы получим

T(n) 
 <= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
 = cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n ai

и теперь каким-то образом мы должны получить ужасную сумму справа от знака плюс, чтобы поглотить cnслева. Если мы просто свяжем это как , мы получим примерно . Но это слишком много - нет места, чтобы выжать2(1/n) ∑i=n/2 to n an2(1/n)(n/2)an = ancn . Итак, давайте расширим сумму, используя формулу арифметического ряда:

i=floor(n/2) to n i  
 = ∑i=1 to n i - ∑i=1 to floor(n/2) i  
 = n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2  
 <= n2/2 - (n/4)2/2  
 = (15/32)n2

где мы используем n как «достаточно большое», чтобы заменить уродливые floor(n/2)факторы гораздо более чистыми (и меньшими) n/4. Теперь мы можем продолжить

cn + 2 (1/n) ∑i=floor(n/2) to n ai,
 <= cn + (2a/n) (15/32) n2
 = n (c + (15/16)a)
 <= an

при условии a > 16c .

Это дает T(n) = O(n). Это ясно Omega(n), так что мы получаем T(n) = Theta(n).

Ин Сяо
источник
12
Быстрый выбор только O (n) в среднем случае. Алгоритм медианы медиан может использоваться для решения задачи за O (n) раз в худшем случае.
Джон Курлак
В чем смысл k > length(A) - length(A2)?
WoooHaaaa
это не O (n), вы снова вызываете функцию как рекурсивную, T (n). Там уже есть O (n) внутри рекурсивной функции T (n), так что, очевидно, не задумываясь, общая сложность будет больше, чем O (n).
user1735921
3
@MrROY Учитывая, что мы разделились Aна A1и A2вокруг разворота, мы это знаем length(A) == length(A1)+length(A2)+1. Таким образом, k > length(A)-length(A2)эквивалентно k > length(A1)+1, что верно, когда kгде-то в A2.
Филипе Гонсалвеш
@ FilipeGonçalves, да, если в сводной таблице нет повторяющихся элементов. len (A1) + len (A2) + K-дубликат = len (A)
d1val
16

Быстрый Google по этому вопросу ('kth самый большой массив элементов') возвратил это: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17

"Make one pass through tracking the three largest values so far." 

(это было специально для 3d крупнейших)

и этот ответ:

Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)
кроличий садок
источник
15
ну, на самом деле это O (n) + O (k log n), которое не уменьшается при значительных значениях K
Джимми
2
Но найти точку вставки в этом двусвязном списке - O (k).
Кирк Штраузер
1
И если k является фиксированным, O (k) = O (1)
Тайлер МакГенри
1
@warren: Big-O приближенный, но вы всегда слишком приблизительный. Например, быстрой сортировкой фактически является O (n ^ 2), поскольку это наихудший случай. это O (n + k log n).
Клавдиу
1
Вы не можете рассматривать k как константу. Возможно, что k = n, и в этом случае временная сложность O (nlogn)
саббир
11

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

вонючий
источник
2
Это то, что быстрый выбор, FWIW.
rogerdpack
6

Спутник программиста для анализа алгоритма дает версию , которая является O (п), хотя автор заявляет , что постоянный фактор настолько высок, вы, вероятно , предпочитают наивные сортировки-The-список-то-выберите метод.

Я ответил на письмо вашего вопроса :)

Джимми
источник
2
Не совсем верно во всех случаях. Я реализовал медиану медиан и сравнил его со встроенным методом сортировки в .NET, и пользовательское решение действительно работает на порядок быстрее. Теперь реальный вопрос: имеет ли это значение для вас в данных обстоятельствах. Написание и отладка 100 строк кода по сравнению с одним вкладчиком окупается, только если этот код будет выполняться так много раз, что пользователь начинает замечать разницу во времени выполнения и испытывает дискомфорт в ожидании завершения операции.
Зоран Хорват
5

Стандартная библиотека C ++ имеет почти такой же вызов функцииnth_element , хотя и изменяет ваши данные. Он ожидал линейного времени выполнения O (N) и также выполняет частичную сортировку.

const int N = ...;
double a[N];
// ... 
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a
Дэвид Неем
источник
1
Нет, ожидаемое среднее время выполнения O (n). Например, быстрой сортировкой в ​​среднем является O (nlogn) с наихудшим случаем O (n ^ 2). Вау, что-то прямо на самом деле не так!
Кирк Штраузер
5
Нет, на самом деле нет ничего плохого в этом ответе. Это работает, и стандарт C ++ требует ожидаемого линейного времени выполнения.
Дэвид Нехм
В интервью меня попросили предположить наличие свободного места O (k), а 'n' очень велико. Я не мог сказать ему решение O (n), так как думал, что nth_element понадобится пробел o (n). Я не прав? Разве базовый алгоритм не основан на быстрой сортировке для nth_element?
Маниш Бафна
4

Хотя не совсем уверен насчет сложности O (n), но он обязательно будет между O (n) и nLog (n). Также обязательно быть ближе к O (n), чем nLog (n). Функция написана на Java

public int quickSelect(ArrayList<Integer>list, int nthSmallest){
    //Choose random number in range of 0 to array length
    Random random =  new Random();
    //This will give random number which is not greater than length - 1
    int pivotIndex = random.nextInt(list.size() - 1); 

    int pivot = list.get(pivotIndex);

    ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
    ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();

    //Split list into two. 
    //Value smaller than pivot should go to smallerNumberList
    //Value greater than pivot should go to greaterNumberList
    //Do nothing for value which is equal to pivot
    for(int i=0; i<list.size(); i++){
        if(list.get(i)<pivot){
            smallerNumberList.add(list.get(i));
        }
        else if(list.get(i)>pivot){
            greaterNumberList.add(list.get(i));
        }
        else{
            //Do nothing
        }
    }

    //If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list 
    if(nthSmallest < smallerNumberList.size()){
        return quickSelect(smallerNumberList, nthSmallest);
    }
    //If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
    //The step is bit tricky. If confusing, please see the above loop once again for clarification.
    else if(nthSmallest > (list.size() - greaterNumberList.size())){
        //nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in 
        //smallerNumberList
        nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
        return quickSelect(greaterNumberList,nthSmallest);
    }
    else{
        return pivot;
    }
}
притхви занкат
источник
Хорошее кодирование, +1. Но нет необходимости использовать дополнительное пространство.
Хенгаме
4

Я реализовал поиск k-го минимума в n несортированных элементах, используя динамическое программирование, в частности метод турниров. Время выполнения O (n + klog (n)). Используемый механизм указан как один из методов на странице Википедии об алгоритме выбора (как указано в одной из публикаций выше). Вы можете прочитать об алгоритме, а также найти код (java) на странице моего блога. Поиск минимума Kth . Кроме того, логика может выполнять частичное упорядочение списка - вернуть первые K min (или max) за O (klog (n)) время.

Хотя предоставленный код приводит к k-му минимуму, аналогичная логика может использоваться для нахождения k-го максимума в O (klog (n)), игнорируя предварительную работу, проделанную для создания дерева турниров.

Малкит С. Бхасин
источник
3

Вы можете сделать это в O (n + kn) = O (n) (для постоянной k) для времени и O (k) для пространства, отслеживая k самых больших элементов, которые вы видели.

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

Приоритетное решение кучи Уоррена, тем не менее, аккуратнее.

Роб Уокер
источник
3
Это будет наихудший случай O (n ^ 2), когда вас попросят наименьший предмет.
Эли
2
«Самый маленький элемент» означает, что k = n, поэтому k больше не является константой.
Тайлер МакГенри
Или, может быть, сохранить кучу (или обращенную кучу, или сбалансированное дерево) самого большого k, который вы когда-либо видели O(n log k)... все еще вырождающегося в O (nlogn) в случае большого k. Я думаю, что это будет хорошо работать для небольших значений k, однако ... возможно, быстрее, чем некоторые другие алгоритмы, упомянутые здесь [???]
rogerdpack
3

Сексуальный быстрый выбор в Python

def quickselect(arr, k):
    '''
     k = 1 returns first element in ascending order.
     can be easily modified to return first element in descending order
    '''

    r = random.randrange(0, len(arr))

    a1 = [i for i in arr if i < arr[r]] '''partition'''
    a2 = [i for i in arr if i > arr[r]]

    if k <= len(a1):
        return quickselect(a1, k)
    elif k > len(arr)-len(a2):
        return quickselect(a2, k - (len(arr) - len(a2)))
    else:
        return arr[r]
Hoder
источник
Хорошее решение, за исключением того, что он возвращает k-й наименьший элемент в несортированном списке. Если поменять операторы сравнения в списке a1 = [i for i in arr if i > arr[r]]и a2 = [i for i in arr if i < arr[r]], вернем k-й по величине элемент.
суждение
Исходя из небольшого теста, даже для больших массивов, сортировать быстрее (с помощью numpy.sortfor numpy arrayили sortedfor) можно быстрее, чем использовать эту ручную реализацию.
Næreen
2

Найдите медиану массива за линейное время, затем используйте процедуру разделения точно так же, как в быстрой сортировке, чтобы разделить массив на две части, значения слева от медианы меньше (<), чем медиана, и справа больше, чем (>) медиана , это тоже может быть сделано во время lineat, теперь, перейдите к той части массива, где лежит k-й элемент, Теперь повторение становится: T (n) = T (n / 2) + cn, что дает мне O (n) в целом.

pranjal
источник
Нет необходимости находить медиану. без медианы ваш подход все еще в порядке.
Хенгаме
2
И как вы находите медиану в линейном времени, смею спросить? ... :)
rogerdpack
2

Ниже приведена ссылка на полную реализацию с довольно подробным объяснением того, как работает алгоритм поиска K-го элемента в несортированном алгоритме. Основная идея заключается в разделении массива, как в QuickSort. Но для того, чтобы избежать крайних случаев (например, когда на каждом шаге выбирается наименьший элемент, так что алгоритм вырождается во время выполнения O (n ^ 2)), применяется специальный выбор, сводный, называемый алгоритмом медианы медиан. Все решение работает за O (n) время в худшем и в среднем случае.

Вот ссылка на полную статью (речь идет о поиске наименьшего K-го элемента, но принцип поиска K-го наибольшего аналогичен ):

Нахождение Kth самого маленького элемента в несортированном массиве

Зоран Хорват
источник
2

В соответствии с этой статьей Нахождение K-го по величине элемента в списке из n элементов следующий алгоритм O(n)в худшем случае займет время.

  1. Разделите массив на n / 5 списков по 5 элементов в каждом.
  2. Найдите медиану в каждом подмассиве из 5 элементов.
  3. Рекурсивно найти медиану всех медиан, назовем это M
  4. Разбиение массива на два подмассива 1-й подмассив содержит элементы больше, чем M, допустим, что этот подмассив равен a1, в то время как другой подмассив содержит элементы меньше M., давайте назовем этот подмассив a2.
  5. Если k <= | a1 |, вернуть выбор (a1, k).
  6. Если k− 1 = | a1 |, вернуть M.
  7. Если k> | a1 | + 1, возврат выбора (a2, k −a1 - 1).

Анализ: как предложено в оригинальной статье:

Мы используем медиану для разделения списка на две половины (первая половина, если k <= n/2 , и вторая половина в противном случае). Этот алгоритм требует времени cnна первом уровне рекурсии для некоторой константы c, cn/2на следующем уровне (поскольку мы повторяем в списке размером n / 2), cn/4на третьем уровне и так далее. Общее время занимает cn + cn/2 + cn/4 + .... = 2cn = o(n).

Почему размер раздела берется 5, а не 3?

Как упоминалось в оригинальной статье :

Разделение списка на 5 обеспечивает наихудшее разделение на 70 - 30. По крайней мере половина медиан, превышающих медиану медиан, следовательно, по крайней мере половина из n / 5 блоков имеет по крайней мере 3 элемента, и это дает 3n/10разделение, которое означает, что другой раздел 7n / 10 в худшем случае. Это дает T(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1худшее время выполнения O(n).

Теперь я попытался реализовать вышеупомянутый алгоритм как:

public static int findKthLargestUsingMedian(Integer[] array, int k) {
        // Step 1: Divide the list into n/5 lists of 5 element each.
        int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
        // Step 2: Find pivotal element aka median of medians.
        int medianOfMedian =  findMedianOfMedians(array, noOfRequiredLists);
        //Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
        List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
        List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
        for (Integer element : array) {
            if (element < medianOfMedian) {
                listWithSmallerNumbers.add(element);
            } else if (element > medianOfMedian) {
                listWithGreaterNumbers.add(element);
            }
        }
        // Next step.
        if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
        else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
        else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
        return -1;
    }

    public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
        int[] medians = new int[noOfRequiredLists];
        for (int count = 0; count < noOfRequiredLists; count++) {
            int startOfPartialArray = 5 * count;
            int endOfPartialArray = startOfPartialArray + 5;
            Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
            // Step 2: Find median of each of these sublists.
            int medianIndex = partialArray.length/2;
            medians[count] = partialArray[medianIndex];
        }
        // Step 3: Find median of the medians.
        return medians[medians.length / 2];
    }

Просто для завершения, другой алгоритм использует очередь приоритетов и требует времени O(nlogn) .

public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
        int p = 0;
        int numElements = nums.length;
        // create priority queue where all the elements of nums will be stored
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // place all the elements of the array to this priority queue
        for (int n : nums) {
            pq.add(n);
        }

        // extract the kth largest element
        while (numElements - k + 1 > 0) {
            p = pq.poll();
            k++;
        }

        return p;
    }

Оба этих алгоритма могут быть протестированы как:

public static void main(String[] args) throws IOException {
        Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
        System.out.println(findKthLargestUsingMedian(numbers, 8));
        System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
    }

Ожидаемый результат: 18 18

akhil_mittal
источник
@rogerdpack Я предоставил ссылку, по которой перешел.
akhil_mittal
2

Как насчет такого рода подхода

Поддержание a buffer of length kи a tmp_max, получение tmp_max равно O (k) и выполняется n раз, что-то вродеO(kn)

введите описание изображения здесь

Это правильно или я что-то упустил?

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

Айшват Сингх
источник
1
Мне нравится, легче понять. Хотя сложность - это O (nk), как вы указали.
Хаджат
1

перебрать список. если текущее значение больше, чем сохраненное наибольшее значение, сохраните его как наибольшее значение и увеличьте 1-4 и 5 выпадет из списка. Если нет, сравните его с номером 2 и сделайте то же самое. Повторите, проверяя все 5 сохраненных значений. это должно сделать это в O (N)

Kevin
источник
Этот «удар» равен O (n), если вы используете массив, или до O (log n) (я думаю), если вы используете лучшую структуру.
Кирк Штраузер
Это не должно быть O (log k) - если список является связанным списком, то добавление нового элемента в верхнюю часть и добавление последнего элемента больше похоже на O (2)
Alnitak
Ударом будет O (k) для списка на основе массива, O (1) для списка с соответствующей связью. В любом случае, этот вопрос обычно предполагает, что он имеет минимальное влияние по сравнению с n, и не вводит больше факторов n.
Бобинц
было бы также O (1), если удар использует кольцевой буфер
Alnitak
1
В любом случае, алгоритм комментария неполон, он не учитывает входящий элемент n, который является новым (например, вторым по величине). В худшем случае, когда каждый элемент в n должен сравниваться с каждым в таблице рекордов, это O (kn), но это все еще, вероятно, означает O (n) с точки зрения вопроса.
Бобинц
1

я хотел бы предложить один ответ

если мы возьмем первые k элементов и отсортируем их в связанный список из k значений

теперь для любого другого значения, даже для наихудшего случая, если мы сделаем вставку сортировки для остальных значений nk, даже в наихудшем случае число сравнений будет k * (nk), а для предыдущих значений k, которые будут отсортированы, пусть будет k * (k- 1) так что получается (nk-k), что есть o (n)

ура


источник
1
сортировка занимает время журнала ... алгоритм должен работать за линейное время
MrDatabase
1

Объяснение алгоритма медианы медиан для нахождения k-го наибольшего целого числа из n можно найти здесь: http://cs.indstate.edu/~spitla/presentation.pdf

Реализация в c ++ ниже:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMedian(vector<int> vec){
//    Find median of a vector
    int median;
    size_t size = vec.size();
    median = vec[(size/2)];
    return median;
}

int findMedianOfMedians(vector<vector<int> > values){
    vector<int> medians;

    for (int i = 0; i < values.size(); i++) {
        int m = findMedian(values[i]);
        medians.push_back(m);
    }

    return findMedian(medians);
}

void selectionByMedianOfMedians(const vector<int> values, int k){
//    Divide the list into n/5 lists of 5 elements each
    vector<vector<int> > vec2D;

    int count = 0;
    while (count != values.size()) {
        int countRow = 0;
        vector<int> row;

        while ((countRow < 5) && (count < values.size())) {
            row.push_back(values[count]);
            count++;
            countRow++;
        }
        vec2D.push_back(row);
    }

    cout<<endl<<endl<<"Printing 2D vector : "<<endl;
    for (int i = 0; i < vec2D.size(); i++) {
        for (int j = 0; j < vec2D[i].size(); j++) {
            cout<<vec2D[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

//    Calculating a new pivot for making splits
    int m = findMedianOfMedians(vec2D);
    cout<<"Median of medians is : "<<m<<endl;

//    Partition the list into unique elements larger than 'm' (call this sublist L1) and
//    those smaller them 'm' (call this sublist L2)
    vector<int> L1, L2;

    for (int i = 0; i < vec2D.size(); i++) {
        for (int j = 0; j < vec2D[i].size(); j++) {
            if (vec2D[i][j] > m) {
                L1.push_back(vec2D[i][j]);
            }else if (vec2D[i][j] < m){
                L2.push_back(vec2D[i][j]);
            }
        }
    }

//    Checking the splits as per the new pivot 'm'
    cout<<endl<<"Printing L1 : "<<endl;
    for (int i = 0; i < L1.size(); i++) {
        cout<<L1[i]<<" ";
    }

    cout<<endl<<endl<<"Printing L2 : "<<endl;
    for (int i = 0; i < L2.size(); i++) {
        cout<<L2[i]<<" ";
    }

//    Recursive calls
    if ((k - 1) == L1.size()) {
        cout<<endl<<endl<<"Answer :"<<m;
    }else if (k <= L1.size()) {
        return selectionByMedianOfMedians(L1, k);
    }else if (k > (L1.size() + 1)){
        return selectionByMedianOfMedians(L2, k-((int)L1.size())-1);
    }

}

int main()
{
    int values[] = {2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};

    vector<int> vec(values, values + 25);

    cout<<"The given array is : "<<endl;
    for (int i = 0; i < vec.size(); i++) {
        cout<<vec[i]<<" ";
    }

    selectionByMedianOfMedians(vec, 8);

    return 0;
}
totjammykd
источник
Это решение не работает. Вам нужно отсортировать массив, прежде чем возвращать медиану для случая 5 элементов.
Агнишом Чаттопадхяй
1

Существует также алгоритм выбора Вирта , который имеет более простую реализацию, чем QuickSelect. Алгоритм выбора Wirth медленнее, чем QuickSelect, но с некоторыми улучшениями он становится быстрее.

Более детально. Используя оптимизацию MODIFIND для Владимира Забродского и выбор центральной точки 3 и уделив некоторое внимание заключительным шагам разделительной части алгоритма, я придумал следующий алгоритм (предположительно названный «LefSelect»):

#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
    int l=0, m = n-1, i=l, j=m;
    float x;

    while (l<m) {
        if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
        if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
        if( a[j] < a[k] ) F_SWAP(a[k],a[j]);

        x=a[k];
        while (j>k & i<k) {
            do i++; while (a[i]<x);
            do j--; while (a[j]>x);

            F_SWAP(a[i],a[j]);
        }
        i++; j--;

        if (j<k) {
            while (a[i]<x) i++;
            l=i; j=m;
        }
        if (k<i) {
            while (x<a[j]) j--;
            m=j; i=l;
        }
    }
    return a[k];
}

В тестах, которые я сделал здесь , LefSelect на 20-30% быстрее, чем QuickSelect.

estama
источник
1

Решение Haskell:

kthElem index list = sort list !! index

withShape ~[]     []     = []
withShape ~(x:xs) (y:ys) = x : withShape xs ys

sort []     = []
sort (x:xs) = (sort ls `withShape` ls) ++ [x] ++ (sort rs `withShape` rs)
  where
   ls = filter (<  x)
   rs = filter (>= x)

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

user3585010
источник
1

Вот реализация C ++ Randomized QuickSelect. Идея состоит в том, чтобы случайным образом выбрать элемент поворота. Чтобы реализовать рандомизированное разделение, мы используем случайную функцию rand (), чтобы сгенерировать индекс между l и r, поменять элемент со случайно сгенерированным индексом на последний элемент и, наконец, вызвать стандартный процесс разделения, который использует последний элемент в качестве pivot.

#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;

int randomPartition(int arr[], int l, int r);

// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method.  ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
    // If k is smaller than number of elements in array
    if (k > 0 && k <= r - l + 1)
    {
        // Partition the array around a random element and
        // get position of pivot element in sorted array
        int pos = randomPartition(arr, l, r);

        // If position is same as k
        if (pos-l == k-1)
            return arr[pos];
        if (pos-l > k-1)  // If position is more, recur for left subarray
            return kthSmallest(arr, l, pos-1, k);

        // Else recur for right subarray
        return kthSmallest(arr, pos+1, r, k-pos+l-1);
    }

    // If k is more than number of elements in array
    return INT_MAX;
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Standard partition process of QuickSort().  It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x) //arr[i] is bigger than arr[j] so swap them
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]); // swap the pivot
    return i;
}

// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
    int n = r-l+1;
    int pivot = rand() % n;
    swap(&arr[l + pivot], &arr[r]);
    return partition(arr, l, r);
}

// Driver program to test above methods
int main()
{
    int arr[] = {12, 3, 5, 7, 4, 19, 26};
    int n = sizeof(arr)/sizeof(arr[0]), k = 3;
    cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
    return 0;
}

Наихудшая временная сложность вышеупомянутого решения - все еще O (n2). В худшем случае, рандомизированная функция всегда может выбрать угловой элемент. Ожидаемая временная сложность вышеупомянутого рандомизированного быстрого выбора составляет Θ (n)

ученик
источник
Хорошее кодирование. Спасибо, что поделились, +1
Hengameh
1
  1. Создана очередь с приоритетами.
  2. Вставьте все элементы в кучу.
  3. Вызовите опрос () k раз.

    public static int getKthLargestElements(int[] arr)
    {
        PriorityQueue<Integer> pq =  new PriorityQueue<>((x , y) -> (y-x));
        //insert all the elements into heap
        for(int ele : arr)
           pq.offer(ele);
        // call poll() k times
        int i=0;
        while(i&lt;k)
         {
           int result = pq.poll();
         } 
       return result;        
    }
    
Бхагвати Малав
источник
0

Это реализация в Javascript.

Если вы отмените ограничение на невозможность изменить массив, вы можете запретить использование дополнительной памяти, используя два индекса для определения «текущего раздела» (в классическом стиле быстрой сортировки - http://www.nczonline.net/blog/2012/ 11/27 / computer-science-in-javascript-quicksort / ).

function kthMax(a, k){
    var size = a.length;

    var pivot = a[ parseInt(Math.random()*size) ]; //Another choice could have been (size / 2) 

    //Create an array with all element lower than the pivot and an array with all element higher than the pivot
    var i, lowerArray = [], upperArray = [];
    for (i = 0; i  < size; i++){
        var current = a[i];

        if (current < pivot) {
            lowerArray.push(current);
        } else if (current > pivot) {
            upperArray.push(current);
        }
    }

    //Which one should I continue with?
    if(k <= upperArray.length) {
        //Upper
        return kthMax(upperArray, k);
    } else {
        var newK = k - (size - lowerArray.length);

        if (newK > 0) {
            ///Lower
            return kthMax(lowerArray, newK);
        } else {
            //None ... it's the current pivot!
            return pivot;
        }   
    }
}  

Если вы хотите проверить, как это работает, вы можете использовать этот вариант:

    function kthMax (a, k, logging) {
         var comparisonCount = 0; //Number of comparison that the algorithm uses
         var memoryCount = 0;     //Number of integers in memory that the algorithm uses
         var _log = logging;

         if(k < 0 || k >= a.length) {
            if (_log) console.log ("k is out of range"); 
            return false;
         }      

         function _kthmax(a, k){
             var size = a.length;
             var pivot = a[parseInt(Math.random()*size)];
             if(_log) console.log("Inputs:", a,  "size="+size, "k="+k, "pivot="+pivot);

             // This should never happen. Just a nice check in this exercise
             // if you are playing with the code to avoid never ending recursion            
             if(typeof pivot === "undefined") {
                 if (_log) console.log ("Ops..."); 
                 return false;
             }

             var i, lowerArray = [], upperArray = [];
             for (i = 0; i  < size; i++){
                 var current = a[i];
                 if (current < pivot) {
                     comparisonCount += 1;
                     memoryCount++;
                     lowerArray.push(current);
                 } else if (current > pivot) {
                     comparisonCount += 2;
                     memoryCount++;
                     upperArray.push(current);
                 }
             }
             if(_log) console.log("Pivoting:",lowerArray, "*"+pivot+"*", upperArray);

             if(k <= upperArray.length) {
                 comparisonCount += 1;
                 return _kthmax(upperArray, k);
             } else if (k > size - lowerArray.length) {
                 comparisonCount += 2;
                 return _kthmax(lowerArray, k - (size - lowerArray.length));
             } else {
                 comparisonCount += 2;
                 return pivot;
             }
     /* 
      * BTW, this is the logic for kthMin if we want to implement that... ;-)
      * 

             if(k <= lowerArray.length) {
                 return kthMin(lowerArray, k);
             } else if (k > size - upperArray.length) {
                 return kthMin(upperArray, k - (size - upperArray.length));
             } else 
                 return pivot;
     */            
         }

         var result = _kthmax(a, k);
         return {result: result, iterations: comparisonCount, memory: memoryCount};
     }

Остальная часть кода просто для создания игровой площадки:

    function getRandomArray (n){
        var ar = [];
        for (var i = 0, l = n; i < l; i++) {
            ar.push(Math.round(Math.random() * l))
        }

        return ar;
    }

    //Create a random array of 50 numbers
    var ar = getRandomArray (50);   

Теперь проведите тесты несколько раз. Из-за Math.random () он будет выдавать каждый раз разные результаты:

    kthMax(ar, 2, true);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 34, true);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);

Если вы тестируете его несколько раз, вы можете даже эмпирически увидеть, что число итераций в среднем составляет O (n) ~ = константа * n, и значение k не влияет на алгоритм.

Крис Синелли
источник
0

Я придумал этот алгоритм и, кажется, O (n):

Допустим, k = 3, и мы хотим найти третий по величине элемент в массиве. Я бы создал три переменные и сравнил бы каждый элемент массива с минимумом этих трех переменных. Если элемент массива больше нашего минимума, мы заменим переменную min значением элемента. Продолжаем то же самое до конца массива. Минимум наших трех переменных является третьим по величине элементом в массиве.

define variables a=0, b=0, c=0
iterate through the array items
    find minimum a,b,c
    if item > min then replace the min variable with item value
    continue until end of array
the minimum of a,b,c is our answer

И, чтобы найти K-й самый большой элемент, нам нужно K переменных.

Пример: (k = 3)

[1,2,4,1,7,3,9,5,6,2,9,8]

Final variable values:

a=7 (answer)
b=8
c=9

Может кто-нибудь, пожалуйста, просмотрите это и дайте мне знать, что мне не хватает?

advncd
источник
0

Вот реализация предложенного алгоритма eladv (я также поместил здесь реализацию со случайным шарниром):

public class Median {

    public static void main(String[] s) {

        int[] test = {4,18,20,3,7,13,5,8,2,1,15,17,25,30,16};
        System.out.println(selectK(test,8));

        /*
        int n = 100000000;
        int[] test = new int[n];
        for(int i=0; i<test.length; i++)
            test[i] = (int)(Math.random()*test.length);

        long start = System.currentTimeMillis();
        random_selectK(test, test.length/2);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        */
    }

    public static int random_selectK(int[] a, int k) {
        if(a.length <= 1)
            return a[0];

        int r = (int)(Math.random() * a.length);
        int p = a[r];

        int small = 0, equal = 0, big = 0;
        for(int i=0; i<a.length; i++) {
            if(a[i] < p) small++;
            else if(a[i] == p) equal++;
            else if(a[i] > p) big++;
        }

        if(k <= small) {
            int[] temp = new int[small];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] < p)
                    temp[j++] = a[i];
            return random_selectK(temp, k);
        }

        else if (k <= small+equal)
            return p;

        else {
            int[] temp = new int[big];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] > p)
                    temp[j++] = a[i];
            return random_selectK(temp,k-small-equal);
        }
    }

    public static int selectK(int[] a, int k) {
        if(a.length <= 5) {
            Arrays.sort(a);
            return a[k-1];
        }

        int p = median_of_medians(a);

        int small = 0, equal = 0, big = 0;
        for(int i=0; i<a.length; i++) {
            if(a[i] < p) small++;
            else if(a[i] == p) equal++;
            else if(a[i] > p) big++;
        }

        if(k <= small) {
            int[] temp = new int[small];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] < p)
                    temp[j++] = a[i];
            return selectK(temp, k);
        }

        else if (k <= small+equal)
            return p;

        else {
            int[] temp = new int[big];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] > p)
                    temp[j++] = a[i];
            return selectK(temp,k-small-equal);
        }
    }

    private static int median_of_medians(int[] a) {
        int[] b = new int[a.length/5];
        int[] temp = new int[5];
        for(int i=0; i<b.length; i++) {
            for(int j=0; j<5; j++)
                temp[j] = a[5*i + j];
            Arrays.sort(temp);
            b[i] = temp[2];
        }

        return selectK(b, b.length/2 + 1);
    }
}
TheLogicGuy
источник
0

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

    public static int kthElInUnsortedList(List<int> list, int k)
    {
        if (list.Count == 1)
            return list[0];

        List<int> left = new List<int>();
        List<int> right = new List<int>();

        int pivotIndex = list.Count / 2;
        int pivot = list[pivotIndex]; //arbitrary

        for (int i = 0; i < list.Count && i != pivotIndex; i++)
        {
            int currentEl = list[i];
            if (currentEl < pivot)
                left.Add(currentEl);
            else
                right.Add(currentEl);
        }

        if (k == left.Count + 1)
            return pivot;

        if (left.Count < k)
            return kthElInUnsortedList(right, k - left.Count - 1);
        else
            return kthElInUnsortedList(left, k);
    }
Lee.O.
источник
0

Вы можете найти k-й наименьший элемент в O (n) времени и постоянном пространстве. Если мы рассмотрим массив только для целых чисел.

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

Вот код для этого

Решение класса:

def _iskthsmallest(self, A, val, k):
    less_count, equal_count = 0, 0
    for i in range(len(A)):
        if A[i] == val: equal_count += 1
        if A[i] < val: less_count += 1

    if less_count >= k: return 1
    if less_count + equal_count < k: return -1
    return 0

def kthsmallest_binary(self, A, min_val, max_val, k):
    if min_val == max_val:
        return min_val
    mid = (min_val + max_val)/2
    iskthsmallest = self._iskthsmallest(A, mid, k)
    if iskthsmallest == 0: return mid
    if iskthsmallest > 0: return self.kthsmallest_binary(A, min_val, mid, k)
    return self.kthsmallest_binary(A, mid+1, max_val, k)

# @param A : tuple of integers
# @param B : integer
# @return an integer
def kthsmallest(self, A, k):
    if not A: return 0
    if k > len(A): return 0
    min_val, max_val = min(A), max(A)
    return self.kthsmallest_binary(A, min_val, max_val, k)
Анубхав Агарвал
источник
0

Существует также один алгоритм, который превосходит алгоритм быстрого выбора. Это называется алгоритм Флойд-Ривец (FR) .

Оригинальная статья: https://doi.org/10.1145/360680.360694

Загружаемая версия: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf

Статья в Википедии https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

Я попытался реализовать быстрый выбор и алгоритм FR в C ++. Также я сравнил их со стандартными реализациями библиотеки C ++ std :: nth_element (который в основном представляет собой интроселектный гибрид quickselect и heapselect). Результатом был быстрый выбор, и nth_element работал в среднем сравнительно, но алгоритм FR работал ок. в два раза быстрее по сравнению с ними.

Пример кода, который я использовал для алгоритма FR:

template <typename T>
T FRselect(std::vector<T>& data, const size_t& n)
{
    if (n == 0)
        return *(std::min_element(data.begin(), data.end()));
    else if (n == data.size() - 1)
        return *(std::max_element(data.begin(), data.end()));
    else
        return _FRselect(data, 0, data.size() - 1, n);
}

template <typename T>
T _FRselect(std::vector<T>& data, const size_t& left, const size_t& right, const size_t& n)
{
    size_t leftIdx = left;
    size_t rightIdx = right;

    while (rightIdx > leftIdx)
    {
        if (rightIdx - leftIdx > 600)
        {
            size_t range = rightIdx - leftIdx + 1;
            long long i = n - (long long)leftIdx + 1;
            long long z = log(range);
            long long s = 0.5 * exp(2 * z / 3);
            long long sd = 0.5 * sqrt(z * s * (range - s) / range) * sgn(i - (long long)range / 2);

            size_t newLeft = fmax(leftIdx, n - i * s / range + sd);
            size_t newRight = fmin(rightIdx, n + (range - i) * s / range + sd);

            _FRselect(data, newLeft, newRight, n);
        }
        T t = data[n];
        size_t i = leftIdx;
        size_t j = rightIdx;
        // arrange pivot and right index
        std::swap(data[leftIdx], data[n]);
        if (data[rightIdx] > t)
            std::swap(data[rightIdx], data[leftIdx]);

        while (i < j)
        {
            std::swap(data[i], data[j]);
            ++i; --j;
            while (data[i] < t) ++i;
            while (data[j] > t) --j;
        }

        if (data[leftIdx] == t)
            std::swap(data[leftIdx], data[j]);
        else
        {
            ++j;
            std::swap(data[j], data[rightIdx]);
        }
        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= n)
            leftIdx = j + 1;
        if (n <= j)
            rightIdx = j - 1;
    }

    return data[leftIdx];
}

template <typename T>
int sgn(T val) {
    return (T(0) < val) - (val < T(0));
}
L'Ахим
источник
-1

Что бы я сделал, это:

initialize empty doubly linked list l
for each element e in array
    if e larger than head(l)
        make e the new head of l
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element

Вы можете просто хранить указатели на первый и последний элемент в связанном списке. Они изменяются только при обновлении списка.

Обновить:

initialize empty sorted tree l
for each element e in array
    if e between head(l) and tail(l)
        insert e into l // O(log k)
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element
Джаспер Беккерс
источник
Что если е меньше, чем голова (л)? Он может быть больше, чем k-й по величине элемент, но никогда не будет добавлен в этот список. Вам нужно будет отсортировать список элементов, чтобы это работало, в порядке возрастания.
Эли
Вы правы, думаю, мне нужно подумать еще немного. :-)
Джаспер Беккерс
Решением было бы проверить, находится ли е между головкой (l) и хвостом (l), и вставить его в правильное положение, если оно есть. Делая это O (кн). Вы можете сделать это O (n log k) при использовании двоичного дерева, которое отслеживает элементы min и max.
Джаспер Беккерс
-1

Сначала мы можем построить BST из несортированного массива, который занимает O (n) времени, и из BST мы можем найти k-й наименьший элемент в O (log (n)), который по всем показателям имеет порядок O (n).

user2601131
источник