una - matrices en java netbeans

Java, encontrando el valor más grande en Kth de la matriz

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cómo encontrar el kth elemento más grande en una matriz no clasificada de longitud n en O (n)? 31 respuestas

Tuve una entrevista con Facebook y me hicieron esta pregunta.

Supongamos que tiene una matriz desordenada con N valores distintos

$ input = [3,6,2,8,9,4,5]

Implementar una función que encuentre el valor más grande Kth.

EG: Si K = 0, devuelve 9. Si K = 1, devuelve 8.

Lo que hice fue este método.

private static int getMax(Integer[] input, int k)
{
List<Integer> list = Arrays.asList(input);
Set<Integer> set = new TreeSet<Integer>(list);
list = new ArrayList<Integer>(set);
int value = (list.size() - 1) - k;
return list.get(value);
}

Acabo de probar y el método funciona bien en función de la pregunta. Sin embargo, dijo el entrevistado, in order to make your life complex! lets assume that your array contains millions of numbers then your listing becomes too slow. What you do in this case? in order to make your life complex! lets assume that your array contains millions of numbers then your listing becomes too slow. What you do in this case? Como sugerencia, sugirió usar min heap . Según mi conocimiento, cada valor hijo de Heap no debe ser más que un valor raíz. Entonces, en este caso, si asumimos que 3 es raíz, entonces 6 es su hijo y su valor es mayor que el valor de la raíz. Probablemente me equivoque, ¿pero qué piensas y cuál es su implementación basada en min heap ?

Answer 1

Él realmente te ha dado toda la respuesta. No solo una pista.

Y su comprensión se basa en el max heap . No min heap . Y su funcionamiento se explica por sí mismo.

En un montón de minutos , la raíz tiene el valor mínimo (menos que sus hijos).

Entonces, lo que necesita es iterar sobre la matriz y rellenar K elementos en min heap . Una vez que está listo, el montón contiene automáticamente el más bajo en la raíz.

Ahora, para cada (siguiente) elemento que lea de la matriz, -> verifique si el valor es mayor que la raíz del montón mínimo. -> En caso afirmativo, elimine la raíz de min heap y agregue el valor.

Después de atravesar toda la matriz, la raíz de min heap contendrá automáticamente el elemento k th más grande.

Y todos los demás elementos (k-1 elementos para ser precisos) en el montón serán mayores que k .

Answer 2

Aquí está la implementación de Min Heap usando PriorityQueue en java. Complejidad: n * log k .

import java.util.PriorityQueue;
public class LargestK {
private static Integer largestK(Integer array[], int k) {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
int i = 0;
while (i<=k) {
queue.add(array[i]);
i++;
}
for (; i<array.length; i++) {
Integer value = queue.peek();
if (array[i] > value) {
queue.poll();
queue.add(array[i]);
}
}
return queue.peek();
}
public static void main(String[] args) {
Integer array[] = new Integer[] {3,6,2,8,9,4,5};
System.out.println(largestK(array, 3));
}
}

Salida: 5

El bucle de código sobre la matriz que es O(n) . El tamaño de la PriorityQueue (Min Heap) es k, por lo que cualquier operación sería log k . En el peor de los casos, en el que todos los números están ordenados por ASC , la complejidad es n*log k , porque para cada elemento debe eliminar la parte superior del montón e insertar un nuevo elemento.

Answer 3

La solución basada en Heap es perfecta si se desconoce el número de elementos en la matriz / secuencia. Pero, qué pasa si son finitos pero aún así desea una solución optimizada en tiempo lineal.

Podemos usar la Selección Rápida, discutida here .

Array = [3,6,2,8,9,4,5]

Vamos a elegir el pivote como primer elemento:

pivote = 3 (al índice 0),

Ahora divida la matriz de tal manera que todos los elementos menores o iguales estén en el lado izquierdo y los números mayores que 3 en el lado derecho. Como se hace en Quick Sort (discutido en mi blog ).

Así que después de la primera pasada - [2, 3 , 6,8,9,4,5]

El índice de pivote es 1 (es decir, es el segundo elemento más bajo). Ahora aplique el mismo proceso de nuevo.

eligió, 6 ahora, el valor en el índice después del pivote anterior - [2,3,4,5, 6 , 8,9]

Así que ahora 6 está en el lugar adecuado.

Verifique si ha encontrado el número apropiado (kth más grande o kth más bajo en cada iteración). Si se encuentra, ya ha terminado, continúe.

Answer 4

Un enfoque para los valores constantes de k es usar una ordenación de inserción parcial.

(Esto asume valores distintos, pero también puede modificarse fácilmente para que funcione con duplicados)

last_min = -inf
output = []
for i in (0..k)
min = +inf
for value in input_array
if value < min and value > last_min
min = value
output[i] = min
print output[k-1]

(Eso es pseudo código, pero debería ser lo suficientemente fácil de implementar en Java).

La complejidad general es O(n*k) , lo que significa que funciona bastante bien si y solo si k es constante o se sabe que es menor que log(n) .

En el lado positivo, es una solución muy simple. En el lado negativo, no es tan eficiente como la solución de pila

Answer 5

Edición: Marque esta answer para la solución O (n).

Probablemente pueda hacer uso de PriorityQueue también para resolver este problema:

public int findKthLargest(int[] 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;
}

Desde el PriorityQueue Java:

Nota de implementación: esta implementación proporciona tiempo O (log (n)) para los métodos de encoing y dequeing ( offer , poll , remove() y add ); tiempo lineal para los métodos remove(Object) y contains(Object) ; y tiempo constante para los métodos de recuperación ( peek , element y size ).

El bucle for se ejecuta n veces y la complejidad del algoritmo anterior es O(nlogn) .