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

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

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

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

 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, nk, ik) 

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

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

Алгоритм 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(n 2 ) 

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

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

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

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

 T(n) <= cn + (1/n) ∑ i=1 to n T(max(i-1, ni)) = cn + (1/n) ∑ i=1 to floor(n/2) T(ni) + (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 . Но это слишком велико - нет места, чтобы втиснуться в дополнительный cn . Итак, давайте разберем сумму, используя формулу арифметического ряда:

 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 <= n 2 /2 - (n/4) 2 /2 = (15/32)n 2 

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

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

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

Это дает 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." 

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

и этот ответ:

 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) 

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

Компонент программиста для анализа алгоритмов дает версию O (n), хотя автор утверждает, что постоянный коэффициент настолько высок, вы, вероятно, предпочтете наивный метод сортировки-списка-потом-select.

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

Стандартная библиотека 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(ArrayListlist, 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 smallerNumberList = new ArrayList(); ArrayList greaterNumberList = new ArrayList(); //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; ipivot){ 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)) время.

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

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

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

Однако приоритетное решение кучи Уоррена является более аккуратным.

Прочтите главу 9, «Медианы» и другие статистические данные из «Введение в алгоритмы» Кормена, 2-е изд. Он имеет ожидаемый алгоритм линейного времени для выбора. Это не то, что люди случайным образом придумали через несколько минут. Сорт кучи, кстати, не будет работать в O (n), это O (nlgn).

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

Сексуальный quickselect в 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] 

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

Вот ссылка на полную статью (речь идет о поиске самого маленького элемента Kth, но принцип тот же, что и для поиска Kth):

Поиск Kth наименьшего элемента в массиве Unsorted

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

  1. Разделите массив на n / 5 списков по 5 элементов каждый.
  2. Найдите медиану в каждом подмножестве из 5 элементов.
  3. Рекурсивно найти медиану всех медианов, назовем ее М
  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 split, что означает, что в последнем случае другой раздел равен 7n / 10. Это дает T(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1 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 listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian List 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) другой алгоритм использует очередь приоритетов и занимает время 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 pq = new PriorityQueue(); // 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

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

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

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

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

ура

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

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

 #include  #include  #include  using namespace std; int findMedian(vector vec){ // Find median of a vector int median; size_t size = vec.size(); median = vec[(size/2)]; return median; } int findMedianOfMedians(vector > values){ vector 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 values, int k){ // Divide the list into n/5 lists of 5 elements each vector > vec2D; int count = 0; while (count != values.size()) { int countRow = 0; vector row; while ((countRow < 5) && (count < values.size())) { row.push_back(values[count]); count++; countRow++; } vec2D.push_back(row); } cout< 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< (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 vec(values, values + 25); cout<<"The given array is : "< 

Существует также алгоритм выбора Вирта , который имеет более простую реализацию, чем QuickSelect. Алгоритм выбора Вирта медленнее, чем 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 (lk & ix); F_SWAP(a[i],a[j]); } i++; j--; if (j 

В тестах, которые я сделал здесь , 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 ++ рандомизированного QuickSelect. Идея состоит в том, чтобы случайно выбрать элемент поворота. Чтобы реализовать рандомизированный раздел, мы используем случайную функцию rand () для генерации индекса между l и r, свопим элемент с произвольно сгенерированным индексом с последним элементом и, наконец, вызываем стандартный процесс разбиения, в котором последний элемент используется как точка поворота.

 #include #include #include 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). В худшем случае рандомизированная функция всегда может выбирать угловой элемент. Ожидаемая временная сложность рандомизированного QuickSelect - это Θ (n)

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

tmp_max buffer of length k и tmp_max , получив tmp_max равным O (k) и выполнив n раз так, чтобы что-то вроде O(kn)

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

Правильно ли, или я что-то упускаю?

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

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

     public static int getKthLargestElements(int[] arr) { PriorityQueue pq = new PriorityQueue<>((x , y) -> (yx)); //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; } в public static int getKthLargestElements(int[] arr) { PriorityQueue pq = new PriorityQueue<>((x , y) -> (yx)); //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.

Если вы отпустите ограничение, которое невозможно изменить в массиве, вы можете запретить использование дополнительной памяти с использованием двух индексов для идентификации «текущего раздела» (в classическом стиле быстрой сортировки – 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}; } 

The rest of the code is just to create some playground:

  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); 

Now, run you tests a few time. Because of the Math.random() it will produce every time different results:

  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); 

If you test it a few times you can see even empirically that the number of iterations is, on average, O(n) ~= constant * n and the value of k does not affect the algorithm.

I came up with this algorithm and seems to be O(n):

Let’s say k=3 and we want to find the 3rd largest item in the array. I would create three variables and compare each item of the array with the minimum of these three variables. If array item is greater than our minimum, we would replace the min variable with the item value. We continue the same thing until end of the array. The minimum of our three variables is the 3rd largest item in the array.

 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 

And, to find Kth largest item we need K variables.

Example: (k=3)

 [1,2,4,1,7,3,9,5,6,2,9,8] Final variable values: a=7 (answer) b=8 c=9 

Can someone please review this and let me know what I am missing?

Here is the implementation of the algorithm eladv suggested(I also put here the implementation with random pivot):

 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 p) big++; } if(k <= small) { int[] temp = new int[small]; for(int i=0, j=0; 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 p) big++; } if(k <= small) { int[] temp = new int[small]; for(int i=0, j=0; 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 

it is similar to the quickSort strategy, where we pick an arbitrary pivot, and bring the smaller elements to its left, and the larger to the right

  public static int kthElInUnsortedList(List list, int k) { if (list.Count == 1) return list[0]; List left = new List(); List right = new List(); 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); } 

You can find the kth smallest element in O(n) time and constant space. If we consider the array is only for integers.

The approach is to do a binary search on the range of Array values. If we have a min_value and a max_value both in integer range, we can do a binary search on that range. We can write a comparator function which will tell us if any value is the kth-smallest or smaller than kth-smallest or bigger than kth-smallest. Do the binary search until you reach the kth-smallest number

Here is the code for that

class Solution:

 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) 

There is also one algorithm, that outperforms quickselect algorithm. It’s called Floyd-Rivets (FR) algorithm .

Original article: https://doi.org/10.1145/360680.360694

Downloadable version: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf

Wikipedia article https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

I tried to implement quickselect and FR algorithm in C++. Also I compared them to the standard C++ library implementations std::nth_element (which is basically introselect hybrid of quickselect and heapselect). The result was quickselect and nth_element ran comparably on average, but FR algorithm ran approx. twice as fast compared to them.

Sample code that I used for FR algorithm:

 template  T FRselect(std::vector& 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  T _FRselect(std::vector& 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  int sgn(T val) { return (T(0) < val) - (val < T(0)); } 

What I would do is this:

 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 

You can simply store pointers to the first and last element in the linked list. They only change when updates to the list are made.

Обновить:

 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 
  • Какая часть бросания Исключения стоит дорого?
  • Каковы реальные накладные расходы на try / catch в C #?
  • Как планируется x86 uops?
  • Насколько быстрее C ++, чем C #?
  • Инструкция INC против ADD 1: Это имеет значение?
  • Есть ли 128-битное целое число в C ++?
  • Любой рекомендуемый учебник по профилированию Java?
  • Насколько медленны исключения .NET?
  • Самый быстрый способ удалить все непечатаемые символы из строки Java
  • Какой был бы самый быстрый метод тестирования на простоту Java?
  • Сравнение двух байтовых массивов в .NET.
  • Давайте будем гением компьютера.