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

220

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?

MrDatabase
fuente
49
Por cierto, casi todos los algoritmos descritos aquí se convierten en O (n ^ 2) u O (n log n) cuando k == n. Es decir, no creo que ninguno de ellos sea O (n) para todos los valores de k. Me modifiqué por señalar esto, pero pensé que deberías saberlo de todos modos.
Kirk Strauser el
19
Los algoritmos de selección pueden ser O (n) para cualquier valor fijo de k. Es decir, puede tener un algoritmo de selección para k = 25 que sea O (n) para cualquier valor de n, y puede hacer esto para cualquier valor particular de k que no esté relacionado con n. El caso en el que el algoritmo ya no es O (n) es cuando el valor de k tiene cierta dependencia del valor de n, como k = n o k = n / 2. Sin embargo, esto no significa que si ejecuta el algoritmo k = 25 en una lista de 25 elementos, de repente ya no es O (n) porque la notación O describe una propiedad del algoritmo, no un particular correr de ello.
Tyler McHenry
1
Me hicieron esta pregunta en una entrevista en Amazon como un caso general de encontrar el segundo elemento más importante. Por cierto, el entrevistador dirigió la entrevista. No pregunté si podría destruir la matriz original (es decir, ordenarla), así que se me ocurrió una solución complicada.
Sambatyon
44
Esta es la Pregunta 9 en la Columna 11 (Clasificación) de Perlas de programación por Jon Bentley.
Qiang Xu
3
@KirkStrauser: Si k == no k == n-1, entonces se vuelve trivial. Podemos obtener max o 2nd max en un solo recorrido. Por lo tanto, los algoritmos proporcionados aquí se usarán prácticamente para valores de k que no pertenecen a {1,2, n-1, n}
Aditya Joshee

Respuestas:

173

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.

eladv
fuente
66
Gracias por las diapositivas.
Kshitij Banerjee
55
¿Por qué tiene que funcionar en talla 5? ¿Por qué no puede funcionar con la talla 3?
Joffrey Baratheon
11
@eladv El enlace de las diapositivas está roto :(
Misha Moroshko
77
@eladv Plese arregla el enlace roto.
maxx777
1
@MishaMoroshko enlace es fija
alfasin
118

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

Ying Xiao
fuente
12
La selección rápida es solo O (n) en el caso promedio. El algoritmo de mediana de medianas se puede utilizar para resolver el problema en el tiempo O (n) en el peor de los casos.
John Kurlak
¿Cuál es el significado de k > length(A) - length(A2)?
WoooHaaaa
esto no es O (n), está llamando a la función nuevamente como recursiva, T (n). Ya hay una O (n) dentro de la función recursiva T (n), por lo que, obviamente, sin pensar, la complejidad general sería mayor que O (n).
user1735921
3
@MrROY Dado que nos dividimos Aen A1y A2alrededor del pivote, lo sabemos length(A) == length(A1)+length(A2)+1. Entonces, k > length(A)-length(A2)es equivalente a k > length(A1)+1, lo cual es cierto cuando kestá en algún lugar A2.
Filipe Gonçalves
@ FilipeGonçalves, sí, si no hay elementos duplicados en el pivote. len (A1) + len (A2) + duplicado K = len (A)
d1val
16

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)
madriguera
fuente
15
bueno, en realidad es O (n) + O (k log n) que no se reduce para valores significativos de K
Jimmy
2
Pero encontrar el punto de inserción en esa lista doblemente vinculada es O (k).
Kirk Strauser
1
Y si k es fijo, O (k) = O (1)
Tyler McHenry el
1
@warren: Big-O es aproximado, pero siempre se sobre-aproxima. Quicksort es en realidad O (n ^ 2), por ejemplo, ya que ese es el peor de los casos. este es O (n + k log n).
Claudiu
1
no puedes tratar k como constante. Es posible que k = n en cuyo caso la complejidad del tiempo sea O (nlogn)
sabbir
11

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

apestoso
fuente
2
Esto es la selección rápida, FWIW.
rogerdpack
6

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

Palanqueta
fuente
2
No es realmente cierto en todos los casos. Implementé una mediana de medianas y la comparé con el método de clasificación incorporado en .NET y la solución personalizada realmente funcionó más rápido por orden de magnitud. Ahora la verdadera pregunta es: ¿eso te importa en determinadas circunstancias? Escribir y depurar 100 líneas de código en comparación con un solo trazador vale la pena si ese código se va a ejecutar tantas veces que el usuario comienza a notar la diferencia en el tiempo de ejecución y siente molestias a la espera de que se complete la operación.
Zoran Horvat
5

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
David Nehme
fuente
1
No, tiene un tiempo de ejecución O (n) promedio esperado . Por ejemplo, quicksort es O (nlogn) en promedio con el peor caso de O (n ^ 2). ¡Guau, algo directo está realmente mal!
Kirk Strauser el
55
No, no hay nada realmente incorrecto con esta respuesta. Funciona y el estándar C ++ requiere un tiempo de ejecución lineal esperado.
David Nehme
En una entrevista me pidieron que asumiera la disponibilidad de espacio de O (k) y 'n' es muy grande. No podía decirle la solución O (n) ya que pensé que nth_element necesitaría espacio o (n). ¿Me equivoco? ¿El algoritmo subyacente no está basado en la clasificación rápida para nth_element?
Manish Baphna
4

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;
    }
}
Prithvi Zankat
fuente
Buena codificación, +1. Pero no hay necesidad de usar espacio extra.
Hengameh
4

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.

Malkit S. Bhasin
fuente
3

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.

Rob Walker
fuente
3
Este sería el peor de los casos de O (n ^ 2) donde se le solicita el elemento más pequeño.
Elie
2
"Elemento más pequeño" significa que k = n, por lo que k ya no es constante.
Tyler McHenry
O tal vez mantenga un montón (o un montón invertido, o un árbol equilibrado) de la k más grande que haya visto hasta ahora O(n log k)... todavía se degenera en O (nlogn) en caso de una gran k. Sin embargo, creo que funcionaría bien para valores pequeños de k ... posiblemente más rápido que algunos de los otros algoritmos mencionados aquí [???]
rogerdpack
3

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]
acaparar
fuente
Buena solución, excepto que esto devuelve el késimo elemento más pequeño en una lista sin ordenar. Invertir los operadores de comparación en las comprensiones de la lista, a1 = [i for i in arr if i > arr[r]]y a2 = [i for i in arr if i < arr[r]], devolverá el kth elemento más grande .
gumption
Desde un pequeño punto de referencia, incluso en grandes series, es más rápido para ordenar (con numpy.sortpor numpy arrayo sortedpara las listas), que utilizar esta aplicación manual.
Næreen
2

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.

pranjal
fuente
No hay necesidad de encontrar la mediana. sin mediana tu enfoque aún está bien.
Hengameh
2
¿Y cómo encuentras la mediana en el tiempo lineal, me atrevo a preguntar? ... :)
rogerdpack
2

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

Zoran Horvat
fuente
2

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

akhil_mittal
fuente
@rogerdpack He proporcionado el enlace que he seguido.
akhil_mittal
2

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

ingrese la descripción de la imagen aquí

¿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.

Aishwat Singh
fuente
1
Me gusta, más fácil de entender. Aunque la complejidad es O (nk) como usted señaló.
Hajjat
1

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)

Kevin
fuente
Esa "protuberancia" es O (n) si está usando una matriz, o baja a O (log n) (creo) si usa una mejor estructura.
Kirk Strauser el
No es necesario que sea O (log k): si la lista es una lista vinculada, agregar el nuevo elemento a la parte superior y soltar el último elemento es más como O (2)
Alnitak
La protuberancia sería O (k) para una lista respaldada por matrices, O (1) para una lista vinculada adecuadamente. De cualquier manera, este tipo de pregunta generalmente asume que tiene un impacto mínimo en comparación con ny no introduce más factores de n.
bobince
también sería O (1) si la protuberancia usa un buffer de anillo
Alnitak
1
De todos modos, el algoritmo del comentario está incompleto, no considera un elemento de n entrante que es el nuevo (por ejemplo) el segundo más grande. El comportamiento en el peor de los casos, donde cada elemento en n debe compararse con cada uno en la tabla de puntuación más alta, es O (kn), pero eso probablemente todavía significa O (n) en términos de la pregunta.
bobince
1

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


fuente
1
clasificación toma tiempo ... nlogn el algoritmo debe ejecutar en un tiempo lineal
MrDatabase
1

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;
}
totjammykd
fuente
Esta solución no funciona. Debe ordenar la matriz antes de devolver la mediana para el caso de 5 elementos.
Agnishom Chattopadhyay
1

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.

estama
fuente
1

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.

usuario3585010
fuente
1

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)

aprendiz
fuente
Buena codificación. Gracias por compartir, +1
Hengameh
1
  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;        
    }
    
Bhagwati Malav
fuente
0

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.

Chris Cinelli
fuente
0

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?

advncd
fuente
0

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);
    }
}
TheLogicGuy
fuente
0

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);
    }
Lee.O.
fuente
0

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)
Anubhav Agarwal
fuente
0

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));
}
L'ahim
fuente
-1

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
Jasper Bekkers
fuente
¿Qué pasa si e es más pequeño que la cabeza (l)? Todavía podría ser más grande que el késimo elemento más grande, pero nunca se agregaría a esa lista. Deberá ordenar la lista de elementos para que esto funcione, en orden ascendente.
Elie
Tienes razón, supongo que tendré que pensarlo un poco más. :-)
Jasper Bekkers
La solución sería verificar si e está entre la cabeza (l) y la cola (l) e insertarlo en la posición correcta si es así. Haciendo esto O (kn). Podría hacerlo O (n log k) cuando use un árbol binario que realice un seguimiento de los elementos min y max.
Jasper Bekkers
-1

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

usuario2601131
fuente