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

Creo que hay una manera de encontrar el elemento kth 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 . Hay un algoritmo aleatorio muy simple (llamado selección rápida ) que toma el O(n)tiempo promedio, el O(n^2)peor de los casos, y un algoritmo no aleatorio bastante complicado (llamado introselect ) que toma el O(n)peor de los casos. Hay información en Wikipedia , pero no es muy buena.

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

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

Si desea un O(n)algoritmo verdadero , en lugar de O(kn)o algo así, entonces debe usar la selección rápida (es básicamente un ordenamiento rápido donde arroja la partición que no le interesa). Mi profesor tiene una gran crítica, 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 de nelementos sin clasificar . Es un algoritmo aleatorio , por lo que calculamos el peor tiempo de ejecución esperado .

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 lanza monedas por nosotros, podemos encontrar que el pivote es siempre el elemento más grande y ksiempre es 1, dando un tiempo de ejecución de

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

Pero si las opciones son realmente aleatorias, el tiempo de ejecución esperado viene dado por

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

donde estamos haciendo la suposición no totalmente razonable de que la recursión siempre aterriza en el mayor de A1o A2.

Supongamos que T(n) <= anpara algunos a. Entonces tenemos

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

y ahora de alguna manera tenemos que obtener la horrenda suma a la derecha del signo más para absorber el cnde la izquierda. Si lo limitamos como , nos ponemos más o menos . Pero esto es demasiado grande: no hay espacio para exprimir un extra . Entonces, expandamos la suma usando la fórmula de la serie aritmética:2(1/n) ∑i=n/2 to n an2(1/n)(n/2)an = ancn

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

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

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

proporcionado a > 16c.

Esto da T(n) = O(n). Está claro Omega(n), así que lo tenemos T(n) = Theta(n).

Un rápido Google sobre eso ('kth mayor elemento de matriz') 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 la clasificación rápida. Elija un elemento al azar y empuje todo más alto o más bajo. En este punto, sabrá en qué elemento eligió realmente, y si es el elemento kth lo que ha hecho, de lo contrario repita con el bin (más alto o más bajo), en el que el elemento kth caería. Estadísticamente hablando, el tiempo se necesita para encontrar el elemento kth crece con n, O (n).

El análisis de algoritmo que acompaña a un programador proporciona una versión que es O (n), aunque el autor afirma que el factor constante es tan alto, que probablemente preferiría el método ingenuo de ordenar la lista y luego seleccionar.

Respondí la carta de tu pregunta :)

La biblioteca estándar de C ++ tiene casi exactamente esa llamada de funciónnth_element , aunque modifica sus datos. Ha esperado un tiempo de ejecución lineal, O (N), y también realiza una ordenación 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 está muy seguro acerca de la complejidad de O (n), pero 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(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;
    }
}

Implementé encontrar kth minimimum en n elementos sin clasificar usando programació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 el Algoritmo de selección (como se indica en una de las publicaciones 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 ordenar parcialmente la lista: devolver los primeros K min (o max) en el tiempo O (klog (n)).

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

Puede hacerlo en O (n + kn) = O (n) (para k constante) para el tiempo y O (k) para el espacio, haciendo un seguimiento de los k elementos más grandes que ha 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.

Sin embargo, la solución de almacenamiento prioritario de Warren es más ordenada.

Selección rápida sexy 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]

Encuentre la mediana de la matriz en tiempo lineal, luego use el procedimiento de partición exactamente como en el ordenamiento rápido para dividir la matriz en dos partes, los valores a la izquierda de la mediana son menores (<) que a la mediana y a la derecha mayores que (>) mediana , eso también se puede hacer en tiempo lineal, ahora, vaya a esa parte de la matriz donde se encuentra el elemento kth, ahora la recurrencia se convierte en: T (n) = T (n / 2) + cn que me da O (n) en general.

A continuación se muestra el enlace a la implementación completa con una explicación bastante extensa sobre cómo funciona el algoritmo para encontrar el elemento Kth en un algoritmo no ordenado. 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 se degenere en O (n ^ 2) tiempo de ejecución), se aplica una selección de pivote especial, llamada algoritmo de mediana de medianas. Toda la solución se ejecuta en 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 Kth más pequeño , pero el principio es el mismo para encontrar el Kth más grande ):

Encontrar el elemento más pequeño de Kth en una matriz sin clasificar

Según este documento, Encontrar el Kth ítem más grande en una lista de n ítems, el siguiente algoritmo llevará O(n)tiempo en el peor de los casos.

1. Divida la matriz en n / 5 listas de 5 elementos cada una.
2. Encuentre la mediana en cada subconjunto de 5 elementos.
3. Encuentre recursivamente la mediana de todas las medianas, llamémosla M
4. Particione la matriz en dos sub-matrices La primera sub-matriz contiene los elementos más grandes que M, digamos que esta sub-matriz es a1, mientras que otra sub-matriz contiene los elementos más pequeños que M., llamemos a esta sub-matriz a2.
5. Si k <= | a1 |, devuelve la selección (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 sugiere 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 cnen el primer nivel de recursión para alguna constante c, cn/2en el siguiente nivel (ya que recurrimos en una lista de tamaño n / 2), cn/4en el tercer nivel, y así sucesivamente. El tiempo total tomado es cn + cn/2 + cn/4 + .... = 2cn = o(n).

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

Como se menciona en el documento original :

La división de la lista por 5 asegura una peor caso de división de 70 - 30. Al menos la mitad de las medianas mayor que la mediana-de-medianas, por lo tanto, al menos la mitad de los n / 5 bloques tienen al menos 3 elementos y esto da una 3n/10división, 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, el peor tiempo de ejecución es O(n).

Ahora he intentado 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<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];
    }

Solo por completar, otro algoritmo hace uso de Priority Queue y lleva 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<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;
    }

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

¿Qué tal este enfoque?

Mantenga a buffer of length ky a tmp_max, obteniendo tmp_max es O (k) y se hace n veces así que algo comoO(kn)

¿Es correcto o me estoy perdiendo algo?

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

iterar a través de la lista. Si el valor actual es mayor que el valor más grande almacenado, guárdelo como el valor más grande y baje el 1-4 y 5 caiga de la lista. Si no, compárelo con el número 2 y haga lo mismo. Repita, verificándolo con 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 vinculada de k valores

ahora para cualquier otro valor, incluso para el peor de los casos, si hacemos una ordenación por inserción para el resto de valores nk, incluso en el peor de los casos, el número de comparaciones será k * (nk) y para que los valores k anteriores se ordenen, déjelo ser k * (k- 1) entonces resulta ser (nk-k) que es o (n)

salud

La explicación del algoritmo de mediana de medianas para encontrar 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 ++ es la siguiente:

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

También existe 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 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 (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];
}

En los puntos de referencia que hice aquí , LefSelect es un 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 calcularla realmente.

Aquí hay una implementación en C ++ de Randomized QuickSelect. La idea es elegir aleatoriamente un elemento pivote. Para implementar una partición aleatoria, usamos una función aleatoria, rand () para generar un índice entre l y r, intercambiamos el elemento en un í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<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;
}

La complejidad de tiempo en el peor de los casos de la solución anterior sigue siendo O (n2). En el peor de los casos, la función aleatoria siempre puede elegir un elemento de esquina. La complejidad temporal esperada de la selección rápida aleatorizada anterior es Θ (n)

1. Tener cola de prioridad creada.
2. Inserte todos los elementos en el montón.

3. Llamar encuesta () k veces.

   public static int getKthLargestElements(int[] arr)
   {
       PriorityQueue<Integer> pq =  new PriorityQueue<>((x , y) -> (y-x));
       //insert all the elements into heap
       for(int ele : arr)
          pq.offer(ele);
       // call poll() k times
       int i=0;
       while(i&lt;k)
        {
          int result = pq.poll();
        } 
      return result;        
   }
   

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

El resto del código es solo para crear un patio de recreo:

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

Ahora, ejecuta tus pruebas unas pocas veces. Debido a Math.random () producirá cada vez resultados diferentes:

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

Si lo prueba varias veces, puede ver incluso empíricamente que el número de iteraciones es, en promedio, O (n) ~ = constante * ny el valor de k no afecta el algoritmo.

Se me ocurrió este algoritmo y parece ser O (n):

Digamos k = 3 y queremos encontrar el tercer elemento más grande de la matriz. Crearía tres variables y compararía cada elemento de la matriz con el mínimo de estas tres variables. Si el elemento de matriz es mayor que nuestro mínimo, reemplazaríamos la variable min con el valor del elemento. Continuamos lo mismo hasta el final de la matriz. El mínimo de nuestras tres variables es el tercer elemento más grande de la matriz.

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

Y, para encontrar el elemento más grande de Kth necesitamos K variables.

Ejemplo: (k = 3)

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

Final variable values:

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

¿Alguien puede revisar esto y decirme lo que me falta?

Aquí está la implementación del algoritmo sugerido por eladv (también puse aquí la implementación con pivote aleatorio):

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

es similar a la estrategia quickSort, donde elegimos un pivote arbitrario y llevamos los elementos más pequeños a su izquierda y los más grandes a la derecha

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

Ir al final de este enlace: ...........

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/

Puedes encontrar el késimo elemento más pequeño en O (n) tiempo y espacio constante. Si consideramos que la matriz es solo para enteros.

El enfoque es hacer una búsqueda binaria en el rango de valores de la matriz. Si tenemos un min_value y un max_value ambos en rango entero, podemos hacer una búsqueda binaria en ese rango. Podemos escribir una función de comparación que nos dirá si algún valor es el kth-más pequeño o más pequeño que kth-más pequeño o más grande que kth-más pequeño. Haga la búsqueda binaria hasta llegar al número k-más pequeño

Aquí está el código para eso

Solución de clase:

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)

También hay un algoritmo que supera el algoritmo de selección rápida. Se llama algoritmo Floyd-Rivets (FR) .

Artículo original: https://doi.org/10.1145/360680.360694

Versión descargable: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf

Artículo de Wikipedia https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

Traté de implementar el algoritmo de selección rápida y FR en C ++. También los comparé con las implementaciones estándar de la biblioteca C ++ std :: nth_element (que es básicamente un híbrido introselect de quickselect y heapselect). El resultado fue selección rápida y nth_element se ejecutó de manera comparable en promedio, pero el algoritmo FR se ejecutó aprox. dos veces más rápido en comparación con ellos.

Código de muestra que utilicé para el algoritmo 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));
}

Lo que haría es esto:

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

Simplemente puede almacenar punteros al primer y último elemento en la lista vinculada. Solo cambian cuando se realizan actualizaciones a la lista.

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

Primero podemos construir un BST a partir de una matriz no ordenada que toma tiempo O (n) y desde el BST podemos encontrar el késimo elemento más pequeño en O (log (n)) que, en general, cuenta en un orden de O (n).