Se le proporciona una matriz A de k valores que contienen valores int en orden ordenado (asec). Encuentre los valores de k superiores (asec) que pueden ser el número de la matriz A, o la suma de dos números de A o la suma de tres números de A.?

Explicación:

La solución a este problema será muy parecida a la operación de fusión de tipo de fusión. Lo que eso significa es que tendremos un conjunto de listas ordenadas que queremos fusionar. Seleccionaremos los elementos más pequeños de esas listas hasta que tengamos k elementos. Esa será nuestra solución.

Primero, ¿cuáles son las listas que necesitamos fusionar? Necesitamos el más pequeño de:

La lista original de números en orden ascendente.
La lista producida por todas las combinaciones de 2 elementos de la lista original en orden ascendente
La lista producida por todas las combinaciones de 3 elementos de la lista original en orden ascendente

Ya tenemos la primera lista, por lo que solo necesitamos generar la segunda y la tercera lista. El enfoque ingenuo sería generar todos los valores en las listas 2 y 3 y luego ordenar los valores. Sin embargo, podríamos hacerlo mejor que eso. Si pensamos en la operación de fusión que estamos haciendo, realmente necesitamos obtener solo el elemento más pequeño de cada lista por iteración. Cada vez que seleccionamos el elemento más pequeño, necesitamos obtener el siguiente elemento más pequeño. Tal vez podamos hacer una función para obtener valores sucesivos de la lista 2 y la lista 3 en tiempo constante.

Sin embargo, si eso fuera posible, podríamos generar una lista ordenada de todas las sumas por pares en tiempo [matemático] \ Theta (n ^ 2) [/ matemático]. La solución más conocida para generar todas las sumas por pares de una lista en orden ordenado es [matemática] \ Theta (n ^ 2 \ lg n) [/ matemática] (vea el Problema 41: Ordenar X + Y (Sumas por parejas). de una manera de hacerlo, ¡hágamelo saber! 🙂 Para los fines de una entrevista, no espero que invente avances en la informática. Por lo tanto, iremos con los ingenuos [matemáticos] \ Theta (n ^ 2 \ lg n) [/ math] solución, que es generar todos los pares y luego ordenar cada par por su suma. Podemos generar todos los pares en [math] \ Theta (n ^ 2) [/ math] time, y nosotros puede ordenarlos en [matemáticas] \ Theta (n ^ 2 \ lg n) [/ matemáticas] tiempo (ya que [matemáticas] n ^ 2 \ lg n ^ 2 [/ matemáticas] es lo mismo que [matemáticas] 2 n ^ 2 \ lg n [/ math]), dándonos nuestra lista ordenada de sumas por pares en el tiempo [math] \ Theta (n ^ 2 \ lg n) [/ math]. Del mismo modo, podemos generar una lista ordenada de todos los 3 elementos sumas en [matemáticas] \ Theta (n ^ 3 \ lg n) [/ matemáticas] tiempo.

Dadas las listas 1, 2 y 3, podemos seleccionar repetidamente el elemento mínimo de las listas 1, 2 o 3 hasta que tengamos elementos [math] k [/ math]. Los elementos [math] k [/ math] que seleccionamos serán nuestra solución.

El tiempo de ejecución general de esta solución es [matemática] \ Theta (n ^ 3 \ lg n) [/ matemática] (suponiendo que [matemática] k [/ matemática] no puede ser mayor que el tamaño de la concatenación de listas 1 , 2 y 3, que es una suposición razonable dado que queremos tener valores reales para devolver).

Notas:

Mi solución resuelve el caso (b) de su enunciado del problema. Por lo tanto, también resuelve el caso (a). No puedo pensar en una forma más eficiente de resolver el problema si necesito satisfacer solo el caso (a), al menos en términos de complejidad asintótica.

Si bien la solución descrita anteriormente es la mejor solución asintótica que se me ocurre, eso no significa que no haya soluciones más eficientes. Sin embargo, cualquier otra solución seguirá teniendo el mismo tiempo de ejecución asintótico (a menos que se idee una mejor solución para el problema abierto que mencioné anteriormente).

Pensemos en cómo podría ser una solución más eficiente. Suponga que [math] k [/ math] es lo suficientemente pequeño como para saber que no necesitaremos generar las listas 1, 2 o 3 en su totalidad. Entonces podríamos truncar esas listas según sea necesario para ahorrar tiempo de ejecución

Truncar la lista 1 es trivial. Truncar las listas 2 y 3 y mantenerlas ordenadas es un poco más difícil. Una posible solución que planteo sería hacer algo similar a la búsqueda binaria. Por ejemplo, supongamos que solo queremos los 5 elementos más pequeños de la lista 2. Podríamos comenzar con dos punteros en la lista 1, uno en el índice 0 y otro en el índice 1. Luego podríamos incrementar un puntero en 1 y disminuir el otro puntero como tantos elementos como sea posible de modo que la suma de los valores señalados por los dos punteros no vaya por debajo de la suma anterior. (Podemos descubrir cuántos elementos para disminuir el otro puntero con una búsqueda binaria modificada). Por lo tanto, podemos encontrar cada elemento sucesivo en la lista 2 en [math] \ Omega (\ lg n) [/ math] time. Sin embargo, debemos tener cuidado si queremos evitar que los punteros se muevan en ciclos. Este método todavía tiene un tiempo de ejecución de [math] \ Theta (n ^ 2 \ lg n) [/ math] si lo usamos para generar todas las sumas por pares [math] n ^ 2 [/ math], pero tiene el beneficio adicional de que podemos tomar el elemento más pequeño paso a paso. Si solo necesitamos algunos elementos de las listas 2 y 3, un método como el que acabo de describir podría ser más ideal.

Implementación de Java:

import java.util.Arrays; public class KSmallestWithCombosOf2And3 { public static void main(String[] args) { int[] A = { 3, 4, 5, 15, 19, 20, 25 }; Integer[] B = KSmallestWithCombosOf2And3(A, 63); System.out.print("[ "); for (int i = 0; i < B.length; i++) { String next = (i == B.length - 1) ? " " : ", "; System.out.print(B[i] + next); } System.out.println("]"); } public static Integer[] KSmallestWithCombosOf2And3(int[] list, int k) { if (k < 1 || list == null || list.length == 0) { return new Integer[0]; } Integer[] result = new Integer[k]; int[][] lists = new int[][] { list, getCombosOf2(list), getCombosOf3(list) }; int[] ptrs = { 0, 0, 0 }; for (int i = 0; i < k; i++) { int min = 0; int minIndex = 0; boolean minAssigned = false; for (int j = 0; j < 3; j++) { if (ptrs[j] < lists[j].length && (lists[j][ptrs[j]] < min || !minAssigned)) { min = lists[j][ptrs[j]]; minIndex = j; minAssigned = true; } } if (minAssigned) { ptrs[minIndex]++; result[i] = min; } else { result[i] = null; } } return result; } public static int[] getCombosOf2(int[] list) { int n = list.length; int numCombos = n * (n - 1) / 2; int[] result = new int[numCombos]; for (int i = 0, c = 0; i < n; i++) { for (int j = 0; j < i; j++, c++) { result[c] = list[i] + list[j]; } } Arrays.sort(result); return result; } public static int[] getCombosOf3(int[] list) { int n = list.length; int numCombos = n * (n - 1) * (n - 2) / 6; int[] result = new int[numCombos]; for (int i = 0, c = 0; i < n; i++) { for (int j = 0; j < i; j++) { for (int k = 0; k < j; k++, c++) { result[c] = list[i] + list[j] + list[k]; } } } Arrays.sort(result); return result; } }

Salida:

  [3, 4, 5, 7, 8, 9, 12, 15, 18, 19, 19, 20, 20, 22, 22, 23, 23, 23, 24, 24, 24,
 25, 25, 26, 27, 27, 28, 28, 28, 29, 29, 30, 32, 33, 34, 34, 35, 37, 38, 38, 39,
 39, 39, 40, 40, 42, 43, 43, 44, 44, 44, 45, 45, 47, 48, 48, 49, 49, 50, 54, 59,
 60, 64]

AlgoritmoAlgoritmosentrevistaentrevistas de programaciónTopCoder