¿Cómo encontrar el k-ésimo elemento más grande en una matriz no ordenada de longitud n en O (n)?

Creo que hay una manera de encontrar el k-ésimo elemento más grande en una matriz sin clasificar de longitud n en O (n). O tal vez es “esperado” O (n) o algo así. ¿Cómo podemos hacer esto?

Esto se llama encontrar la estadística de orden k-ésimo . Hay un algoritmo aleatorizado muy simple (llamado selección rápida ) que toma el tiempo promedio de O(n) , O(n^2) peor tiempo de caso y un algoritmo bastante complejo no aleatorizado (llamado introselect ) que toma O(n) peor tiempo de caso. Hay algo de información en Wikipedia , pero no es muy bueno.

Todo lo que necesitas está en estas diapositivas de PowerPoint . Solo para extraer el algoritmo básico del algoritmo O(n) peor caso (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) 

También está muy bien detallado en el libro Introducción a los algoritmos de Cormen et al.

Si quieres un verdadero algoritmo de O(n) , a diferencia de O(kn) o algo así, entonces debes usar quickselect (básicamente es quicksort donde tiras la partición en la que no estás interesado). Mi prof tiene una gran descripción, con el análisis de tiempo de ejecución: ( referencia )

El algoritmo QuickSelect encuentra rápidamente el k-ésimo elemento más pequeño de una matriz no ordenada de n elementos. Es un algoritmo aleatorizado , por lo que calculamos el tiempo de ejecución esperado en el peor de los casos.

Aquí está el algoritmo.

 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 

¿Cuál es el tiempo de ejecución de este algoritmo? Si el adversario arroja monedas por nosotros, podemos encontrar que el pivote es siempre el elemento más grande y k es siempre 1, lo que da un tiempo de ejecución de

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

Pero si las elecciones son de hecho al azar, el tiempo de ejecución esperado está dado por

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

donde estamos haciendo la suposición no del todo razonable de que la recursión siempre aterriza en el mayor de A1 o A2 .

Supongamos que T(n) <= an para algunos a . Entonces obtenemos

 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 

y ahora de alguna manera tenemos que obtener la sum horrenda a la derecha del signo más para absorber el cn de la izquierda. Si lo limitamos como 2(1/n) ∑ i=n/2 to n an , obtenemos aproximadamente 2(1/n)(n/2)an = an . Pero esto es demasiado grande, no hay espacio para meter un cn adicional. Así que expandamos la sum usando la fórmula de la serie aritmética:

 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 

donde tomamos ventaja de que n es "suficientemente grande" para reemplazar los factores del floor(n/2) feo floor(n/2) con el n/4 mucho más limpio (y más pequeño). Ahora podemos continuar con

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

proporcionado a > 16c .

Esto le da a T(n) = O(n) . Es claramente Omega(n) , entonces obtenemos T(n) = Theta(n) .

Un Google rápido sobre eso (‘kthmatriz de elementos más grande’) devolvió esto: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17

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

(fue específicamente para 3d más grande)

y esta respuesta:

 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) 

Te gusta quicksort. Elige un elemento al azar y empuja todo, ya sea más alto o más bajo. En este punto, sabrá qué elemento eligió realmente, y si es el elemento k, ya terminó, de lo contrario, repite con el bin (mayor o menor), donde caería el elemento k. Estadísticamente hablando, el tiempo se necesita encontrar que el elemento kth crece con n, O (n).

El Compañero de Progtwigdor para el Análisis de Algoritmos proporciona una versión que es O (n), aunque el autor afirma que el factor constante es tan alto, probablemente prefiera el método ingenuo de ordenar-y-seleccionar.

Respondí la letra de tu pregunta 🙂

La biblioteca estándar de C ++ tiene casi exactamente esa función llamada nth_element , aunque modifica sus datos. Ha esperado un tiempo de ejecución lineal, O (N), y también hace un tipo parcial.

 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 

Aunque no estoy muy seguro sobre la complejidad de O (n), seguramente estará entre O (n) y nLog (n). También asegúrese de estar más cerca de O (n) que nLog (n). La función está escrita en 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; } } 

Implementé la búsqueda de kth minimimum en n elementos no clasificados utilizando progtwigción dinámica, específicamente el método de torneo. El tiempo de ejecución es O (n + klog (n)). El mecanismo utilizado se enumera como uno de los métodos en la página de Wikipedia sobre Algoritmo de selección (como se indica en uno de los mensajes anteriores). Puede leer sobre el algoritmo y también encontrar el código (java) en la página de mi blog Finding Kth Minimum . Además, la lógica puede hacer un orden parcial de la lista – devuelva primero K min (o max) en O (klog (n)) tiempo.

Aunque el código proporcionó el resultado kth mínimo, se puede emplear una lógica similar para encontrar kth máximo en O (klog (n)), ignorando el trabajo previo realizado para crear el árbol del torneo.

Puedes hacerlo en O (n + kn) = O (n) (para la constante k) para el tiempo y O (k) para el espacio, haciendo un seguimiento de los k elementos más grandes que has visto.

Para cada elemento de la matriz, puede escanear la lista de k más grande y reemplazar el elemento más pequeño con el nuevo si es más grande.

La solución de stack de prioridad de Warren es más ordenada.

Lea el Capítulo 9, Medianas y otras estadísticas de la “Introducción a los algoritmos” de Cormen, 2da. Edición. Tiene un algoritmo de tiempo lineal esperado para la selección. No es algo que la gente pueda encontrar al azar en unos minutos. Un montón, por cierto, no funcionará en O (n), es O (nlgn).

Encuentre la mediana de la matriz en tiempo lineal, luego use el procedimiento de partición exactamente como en la solución rápida para dividir la matriz en dos partes, valores a la izquierda de la mediana menor (<) que la mediana y hacia la derecha mayor que (>) mediana , eso también se puede hacer en línea en el tiempo, ahora, vaya a esa parte de la matriz donde se encuentra el elemento k, Ahora la recurrencia se convierte en: T (n) = T (n / 2) + cn que me da O (n) general.

Sexy quickselect en 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] 

A continuación se muestra el enlace a la implementación completa con una explicación bastante extensa de cómo funciona el algoritmo para encontrar el elemento Kth en un algoritmo sin clasificar. La idea básica es dividir la matriz como en QuickSort. Pero para evitar casos extremos (por ejemplo, cuando se elige el elemento más pequeño como pivote en cada paso, de modo que el algoritmo degenera en O (n ^ 2) tiempo de ejecución), se aplica una selección de pivote especial, llamada algoritmo de mediana de las medianas. La solución completa se ejecuta en el tiempo O (n) en el peor y en el caso promedio.

Aquí hay un enlace al artículo completo (se trata de encontrar el elemento K más pequeño , pero el principio es el mismo para encontrar Kth más grande ):

Encontrar Kth Smallest Element en una matriz no ordenada

Según este artículo Encontrando el K-ésimo ítem más grande en una lista de n ítems, el siguiente algoritmo tomará el tiempo de O(n) en el peor de los casos.

  1. Divida la matriz en n / 5 listas de 5 elementos cada una.
  2. Encuentra la mediana en cada sub conjunto de 5 elementos.
  3. Encuentre recursivamente la mediana de todas las medianas, llamemos M
  4. Partición de la matriz en dos submatriz 1ra subarreglo contiene los elementos más grandes que M, digamos que esta subarranque es a1, mientras que otra submatriz contiene los elementos más pequeños que M., llamemos a esta sub-matriz a2.
  5. Si k <= | a1 |, selección de retorno (a1, k).
  6. Si k- 1 = | a1 |, devuelve M.
  7. Si k> | a1 | + 1, selección de retorno (a2, k -a1 – 1).

Análisis: Como se sugirió en el documento original:

Usamos la mediana para dividir la lista en dos mitades (la primera mitad, si k <= n/2 , y la segunda mitad de lo contrario). Este algoritmo toma tiempo cn en el primer nivel de recursión para alguna constante c , cn/2 en el siguiente nivel (ya que recursemos en una lista de tamaño n / 2), cn/4 en el tercer nivel, y así sucesivamente. El tiempo total tomado es cn + cn/2 + cn/4 + .... = 2cn = o(n) .

¿Por qué se toma el tamaño de la partición 5 y no 3?

Como se menciona en el documento original:

Dividir la lista por 5 asegura una separación del peor de los casos de 70 a 30. Al menos la mitad de las medianas son mayores que la mediana de las medianas, por lo tanto, al menos la mitad de los n / 5 bloques tienen al menos 3 elementos y esto da un 3n/10 dividir, lo que significa que la otra partición es 7n / 10 en el peor de los casos. Eso da 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 , el tiempo de ejecución del peor de los casos es O(n) .

Ahora he tratado de implementar el algoritmo anterior como:

 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]; } 

Solo para completar, otro algoritmo utiliza Priority Queue y toma tiempo 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; } 

Ambos algoritmos se pueden probar como:

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

Como resultado esperado es: 18 18

iterar a través de la lista. si el valor actual es mayor que el valor más grande almacenado, almacénelo como el valor más grande y baje el 1-4 y 5 gotas de la lista. Si no, compáralo con el número 2 y haz lo mismo. Repita, verificándolo contra los 5 valores almacenados. esto debería hacerlo en O (n)

me gustaría sugerir una respuesta

si tomamos los primeros k elementos y los clasificamos en una lista enlazada de k valores

ahora para cualquier otro valor, incluso para el peor de los casos, si realizamos la ordenación por inserción para los valores de descanso nk, incluso en el peor de los casos el número de comparaciones será k * (nk) y los valores prev k se clasificarán, deje que sea k * (k- 1) por lo que resulta ser (nk-k) que es o (n)

aclamaciones

La explicación del algoritmo de la mediana de las medianas para hallar el k-ésimo entero más grande de n se puede encontrar aquí: http://cs.indstate.edu/~spitla/presentation.pdf

La implementación en c ++ está a continuación:

 #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 : "< 

También está el algoritmo de selección de Wirth , que tiene una implementación más simple que QuickSelect. El algoritmo de selección de Wirth es más lento que QuickSelect, pero con algunas mejoras se vuelve más rápido.

Con más detalle. Utilizando la optimización MODIFIND de Vladimir Zabrodsky y la selección de pivote de la mediana de 3 y prestando atención a los pasos finales de la parte de partición del algoritmo, se me ocurrió el siguiente algoritmo (imaginablemente llamado “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 

En los puntos de referencia que hice aquí , LefSelect es 20-30% más rápido que QuickSelect.

Solución 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) 

Esto implementa la mediana de soluciones medianas utilizando el método withShape para descubrir el tamaño de una partición sin realmente calcularla.

Aquí hay una implementación en C ++ de Selección rápida aleatorizada. La idea es elegir aleatoriamente un elemento pivote. Para implementar la partición aleatorizada, usamos una función aleatoria, rand () para generar un índice entre l y r, intercambiamos el elemento en el índice generado aleatoriamente con el último elemento y finalmente llamamos al proceso de partición estándar que usa el último elemento como pivote.

 #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; } 

La peor complejidad de tiempo de la solución anterior sigue siendo O (n2). En el peor de los casos, la función aleatorizada siempre puede elegir un elemento de esquina. La complejidad de tiempo esperada de QuickSelect aleatorio anterior es Θ (n)

¿Qué tal este enfoque?

Mantenga un buffer of length k un tmp_max , obtener tmp_max es O (k) y se hace n veces así que algo así como O(kn)

enter image description here

¿Está bien o me estoy perdiendo algo?

Aunque no supera el caso promedio de selección rápida y el peor caso de método de estadísticas medianas, es bastante fácil de comprender e implementar.

  1. Tener cola de prioridad creada.
  2. Inserta todos los elementos en el montón.
  3. Call poll () k veces.

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

Esta es una implementación en Javascript.

Si libera la restricción de que no puede modificar la matriz, puede evitar el uso de memoria adicional utilizando dos índices para identificar la “partición actual” (en el estilo clásico de la colección rápida – 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; } } } 

Si desea probar cómo funciona, puede usar esta variación:

  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.

Actualizar:

 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