Как найти k-й по величине элемент в несортированном массиве длины n в O(n)?
https://stackoverflow.com/questions/251781
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я полагаю, что есть способ найти k-й по величине элемент в несортированном массиве длины n в O (n).Или, возможно, это "ожидаемый" O (n) или что-то в этом роде.Как мы можем это сделать?
Решение
Это называется поиском статистики k-го порядка . Существует очень простой рандомизированный алгоритм (называемый quickselect ), который принимает O(n) среднее время, O(n^2) время наихудшего случая, и довольно сложный нерандомизированный алгоритм (называемый introselect ) принимая <=> время наихудшего случая. В Википедии есть некоторая информация, но она не очень хорошая.
Все, что вам нужно, находится в эти слайды PowerPoint . Просто для извлечения основного алгоритма <=> алгоритма наихудшего случая (интроселект):
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)
Это также очень подробно описано в книге «Введение в алгоритмы» Кормена и др.
Другие советы
Если вам нужен истинный O(n) алгоритм, а не O(kn) или что-то в этом роде, вам следует использовать быстрый выбор (в основном это быстрая сортировка, когда вы выбрасываете раздел, который вам не интересен). У моего профессора отличная рецензия с анализом времени выполнения: ( ссылка )
Алгоритм QuickSelect быстро находит k-й наименьший элемент из несортированного массива из n элементов. Это RandomizedAlgorithm , поэтому мы рассчитываем ожидаемый ожидаемый время работы.
Вот алгоритм.
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 an, мы получим примерно 2(1/n)(n/2)an = an. Но это слишком много - нет места, чтобы втиснуть лишнее floor(n/2). Итак, давайте расширим сумму, используя формулу арифметического ряда:
∑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 как " достаточно большой " заменить уродливые n/4 факторы гораздо чище (и меньше) a > 16c. Теперь мы можем продолжить с
cn + 2 (1/n) ∑i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= an предоставлено T(n) = O(n).
Это дает Omega(n). Это ясно T(n) = Theta(n), поэтому мы получаем <=>.
Быстрый 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)
Вам нравится быстрая сортировка. Выберите элемент наугад и засуньте все выше или ниже. В этот момент вы будете знать, какой элемент вы на самом деле выбрали, и если это k-й элемент, который вы сделали, в противном случае вы повторяете с корзиной (выше или ниже), что k-й элемент попадет. По статистике, время требуется, чтобы найти, что k-й элемент растет с n, O (n).
Сопутствующий программисту анализ алгоритмов дает версию, что равен O (n), хотя автор утверждает, что постоянный коэффициент очень высок , вы, вероятно, предпочтете наивный метод сортировки списка-потом-выбора.
Я ответил на письмо вашего вопроса:)
Стандартная библиотека 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
Хотя не совсем уверен насчет сложности 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;
}
}
Я реализовал поиск k-го минимума в n несортированных элементах, используя динамическое программирование, в частности метод турниров. Время выполнения O (n + klog (n)). Используемый механизм указан как один из методов на странице Википедии об алгоритме выбора (как указано в одной из публикаций выше). Вы можете прочитать об алгоритме, а также найти код (java) на странице моего блога Нахождение минимума Kth . Кроме того, логика может выполнять частичное упорядочение списка - возвращать первые K min (или max) за O (klog (n)) время.
Несмотря на то, что код обеспечивает результат k-го минимума, аналогичная логика может использоваться для нахождения k-го максимума в O (klog (n)), игнорируя предварительную работу, проделанную для создания дерева турниров.
Вы можете сделать это в O (n + kn) = O (n) (для постоянной k) для времени и O (k) для пространства, отслеживая k самых больших элементов, которые вы видели.
Для каждого элемента в массиве вы можете просмотреть список k самых больших и заменить наименьший элемент новым, если он больше.
Приоритетное решение для кучи Уоррена более аккуратное.
Сексуальная быстрая выборка в 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]
Найдите медиану массива за линейное время, затем используйте процедуру разделения точно так же, как в быстрой сортировке, чтобы разделить массив на две части, значения слева от медианы меньше (<), чем медиана, и до прямо больше (>) медианы, это тоже можно сделать за линейное время, теперь перейдем к той части массива, где лежит k-й элемент, Теперь повторение становится: T (n) = T (n / 2) + cn что дает мне O (N) в целом.
Ниже приведена ссылка на полную реализацию с довольно подробным объяснением того, как работает алгоритм поиска K-го элемента в несортированном алгоритме.Основная идея состоит в том, чтобы разбить массив на разделы, как в QuickSort.Но для того, чтобы избежать крайних случаев (например,когда наименьший элемент выбирается в качестве опорного на каждом шаге, так что алгоритм вырождается за O (n ^ 2) времени выполнения), применяется специальный выбор опорного элемента, называемый алгоритмом медианы медиан.Все решение выполняется за O (n) раз в худшем и в среднем случаях.
Вот ссылка на полную статью (речь идет о поиске Kth самый маленький элемент, но принцип тот же для нахождения K-го самый большой):
Согласно этой статье Поиск K-го по величине элемента в списке из n элементов следующий алгоритм в худшем случае займет O(n) время.
Анализ . Как указано в оригинальной статье:
Мы используем медиану для разбиения списка на две половины (первая половина, если
k <= n/2, а во второй половине иначе). Этот алгоритм занимает времяcnна первом уровне рекурсии для некоторой константыc,cn/2на следующий уровень (поскольку мы выбираем список размером n / 2),cn/4на третий уровень и тд. Общее время занялоcn + cn/2 + cn/4 + .... = 2cn = o(n).
Почему размер раздела взят 5, а не 3?
Как упоминалось в оригинальной статье :
Разделение списка на 5 обеспечивает наихудшее разделение на 70 & # 8722; 30. Атлет половина медиан, превышающих медиану медиан, следовательно, по крайней мере половина блоков n / 5 имеет по крайней мере 3 элемента, и это дает
3n/10split, что означает, что другой раздел равен 7n / 10 в худшем случае. Это даетT(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1время работы в худшем случаеO(nlogn).
Теперь я попытался реализовать описанный выше алгоритм следующим образом:
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];
}
Просто для завершения другой алгоритм использует очередь приоритетов и занимает время 18
18.
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));
}
Ожидаемый результат: <=>
Как насчет такого рода подхода
Поддерживайте buffer of length k и tmp_max, получая tmp_max - O (k) и выполняется n раз, что-то вроде O(kn)
Это правильно или я что-то упустил?
Хотя он не превосходит средний случай быстрого выбора и наихудший случай метода средней статистики, но его довольно легко понять и реализовать.
итерируйте по списку. если текущее значение больше, чем сохраненное наибольшее значение, сохраните его как наибольшее значение и увеличьте 1-4 и 5 выпадет из списка. Если нет, сравните его с номером 2 и сделайте то же самое. Повторите, проверяя все 5 сохраненных значений. это должно сделать это в O (N)
Я хотел бы предложить один ответ
если мы возьмем первые k элементов и отсортируем их в связанный список из k значений
теперь для любого другого значения, даже для наихудшего случая, если мы выполним сортировку вставкой для остальных значений nk, даже в наихудшем случае число сравнений будет равно k * (nk), а для значений предыдущего k, которые будут отсортированы, оно будет равно k * (k-1), так что получается (nk-k), который равен o (n)
ура
Объяснение алгоритма медианы медиан для нахождения 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;
}
Существует также алгоритм выбора Вирта , который имеет более простую реализацию, чем QuickSelect. Алгоритм выбора Wirth медленнее, чем QuickSelect, но с некоторыми улучшениями он становится быстрее.
Более подробно. Используя оптимизацию MODIFIND Владимира Забродского и выбор центральной оси 3 и уделив некоторое внимание заключительным шагам разделительной части алгоритма, я придумал следующий алгоритм (предположительно названный & Quot; LefSelect Quot;):
#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.
Решение 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 для определения размера раздела без фактического его вычисления.
Вот реализация 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). В худшем случае, случайная функция всегда может выбрать угловой элемент. Ожидаемая временная сложность вышеупомянутого рандомизированного быстрого выбора составляет & # 920; (n)
Вызовите опрос () 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<k)
{
int result = pq.poll();
}
return result;
}
Это реализация в 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) ~ = constant * n и значение k не влияет на алгоритм.
Я придумал этот алгоритм и похоже, что 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
Может ли кто-нибудь проверить это и сообщить, что мне не хватает?
Вот реализация предложенного алгоритма 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);
}
}
она похожа на стратегию быстрой сортировки, где мы выбираем произвольный шарнир и выводим меньшие элементы слева и большие справа
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);
}
Перейти к концу этой ссылки: ...........
Вы можете найти 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)
Существует также один алгоритм, который превосходит алгоритм быстрого выбора. Это называется алгоритм Флойд-Ривец (FR) .
Оригинальная статья: https://doi.org/10.1145/360680.360694
Загружаемая версия: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108 & amp; rep = rep1 & amp; 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));
}
То, что я бы сделал, это:
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
Сначала мы можем построить BST из несортированного массива, который занимает O (n) времени, а из BST мы можем найти k-й наименьший элемент в O (log (n)), который по всем показателям считается порядка O (n). .
