sort bubble algorithms java arrays algorithm time-complexity minimum

java - bubble - sorting algorithms



Encontrar dos elementos no subsiguientes en la matriz cuya suma es mínima (12)

Introducción: Hasta donde pude buscar, esta pregunta no se hizo en SO todavía.
Esta es una pregunta de entrevista.
Ni siquiera estoy buscando específicamente una solución de código, cualquier algoritmo / pseudocódigo funcionará.

El problema: dada una matriz de enteros int[] A y su tamaño N , encuentre 2 elementos no subsiguientes (no pueden ser adyacentes en la matriz) con suma mínima. Además, la respuesta no debe contener el primer o el último elemento (índice 0 y n-1 ). También la solución debe estar en O(n) complejidad de tiempo y espacio.

Por ejemplo, cuando A = [5, 2, 4, 6, 3, 7] la respuesta es 5 , ya que 2+3=5 .
Cuando A = [1, 2, 3, 3, 2, 1] la respuesta es 4 , ya que 2+2=4 y no puede elegir ninguno de los 1 ya que están en los extremos de la matriz.

Intento: al principio pensé que uno de los números de la solución debía ser el más pequeño de la matriz (además del primero y el último), pero esto se refutó rápidamente con el contraejemplo.
A = [4, 2, 1, 2, 4] -> 4 (2+2)

Entonces pensé que si encontraba los 2 números más pequeños (además del primero y el último) en la matriz, la solución sería esos dos. Obviamente, esto falló rápidamente porque no puedo elegir 2 números adyacentes, y si tengo que elegir números no adyacentes, esta es la definición de la pregunta :).

Finalmente , pensé, bueno, solo encontraré los 3 números más pequeños (además del primero y el último) en la matriz, y la solución tendrá que ser dos de esos, ya que dos de ellos no deben estar adyacentes entre sí. Esto también falló debido a A = [2, 2, 1, 2, 4, 2, 6] -> 2+1=3 , lo que parece funcionar porque encontraré 2, 1, 2 , pero asumiendo que estoy encontrando el 2, 1, 2 en los índices 1, 2, 3 esto no necesariamente funcionará (lo haría si encontrara específicamente el 2 en el índice 5 pero lamentablemente no puedo garantizarlo).

Pregunta: Ahora estoy perplejo, ¿alguien puede idear una solución / idea que funcione?

  1. Encuentra el número más pequeño al lado del primero y el último.

  2. Encuentre el segundo más pequeño que no sea un vecino del primero y no el primero o el último en la matriz. Luego construye la suma.

    • Si el primer elemento es el segundo o el penúltimo elemento, ya tiene la solución.

  3. De lo contrario calcule la suma de ambos vecinos del primer número. Compruebe si es más pequeño que la primera suma

    • Si no: toma la primera suma
    • de lo contrario toma la segunda

Esto siempre funcionará porque si la primera suma no es la respuesta, eso significa que el primer número no puede ser parte de la solución. Y eso, por otra parte, significa que la solución puede ser la segunda suma.

Al elaborar la respuesta above , necesitaría una ordenación por inserción modificada para rastrear los cuatro valores más pequeños y los índices correspondientes (una matriz de 4 elementos para cada uno).

Una vez encontrada, la solución sería el primer par cuya diferencia en los índices sería más de 1 y cuya suma sea la menor.

La solución es uno de (0,1) o (0,2) o (0,3) o (1,2) o (1,3) o (2,3) donde los valores indican los índices de la matriz que a su vez rastrea la posición de los elementos reales en la matriz.

También necesitaría manejar el caso especial para la longitud de matriz 5 ( arr/[1]+arr[3] ) y un error para las matrices menores de 5 .

Algoritmo:

  1. Encuentra lo mínimo, evitando los índices finales. (1 O (n) pase)
  2. Encuentre el mínimo, evitando los índices finales y el índice de (1) y los índices adyacentes. (1 O (n) pase)
  3. Encuentre el mínimo, evitando los índices finales y el índice de (1) (1 O (n) pasada)
  4. Encuentre el mínimo, evitando los índices finales y el índice de (3) y los índices adyacentes. (1 O (n) pase)
  5. Devuelva el mínimo de las sumas (1) + (2), (3) + (4), si existen.

Los pases 3 y 4 están destinados a pasar el caso [4, 2, 1, 2, 4] = 4 al encontrar ambos 2s.

public static int minSumNonAdjNonEnd(int[] array) { // 1. Find minimum int minIdx1 = -1; int minValue1 = Integer.MAX_VALUE; for (int i = 1; i < array.length - 1; i++) { if (array[i] < minValue1) { minIdx1 = i; minValue1 = array[i]; } } // 2. Find minimum not among (1) or adjacents. int minIdx2 = -1; int minValue2 = Integer.MAX_VALUE; for (int i = 1; i < array.length - 1; i++) { if ((i < minIdx1 - 1 || i > minIdx1 + 1) && (array[i] < minValue2)) { minIdx2 = i; minValue2 = array[i]; } } boolean sum1Exists = (minIdx1 > -1 && minIdx2 > -1); int sum1 = minValue1 + minValue2; // 3. Find minimum not among (1). int minIdx3 = -1; int minValue3 = Integer.MAX_VALUE; for (int i = 1; i < array.length - 1; i++) { if ((i != minIdx1) && (array[i] < minValue3)) { minIdx3 = i; minValue3 = array[i]; } } // 4. Find minimum not among(3) or adjacents. int minIdx4 = -1; int minValue4 = Integer.MAX_VALUE; for (int i = 1; i < array.length - 1; i++) { if ((i < minIdx3 - 1 || i > minIdx3 + 1) && (array[i] < minValue4)) { minIdx4 = i; minValue4 = array[i]; } } boolean sum2Exists = (minIdx3 > -1 && minIdx4 > -1); int sum2 = minValue3 + minValue4; if (sum1Exists) { if (sum2Exists) return Math.min(sum1, sum2); else return sum1; } else { if (sum2Exists) return sum2; else throw new IllegalArgumentException("impossible"); } }

Esto realiza 4 búsquedas lineales, para una complejidad de O (n).

Casos de prueba:

System.out.println(minSumNonAdjNonEnd(new int[] {5, 2, 4, 6, 3, 7})); System.out.println(minSumNonAdjNonEnd(new int[] {1, 2, 3, 3, 2, 1})); System.out.println(minSumNonAdjNonEnd(new int[] {4, 2, 1, 2, 4})); System.out.println(minSumNonAdjNonEnd(new int[] {2, 2, 1, 2, 4, 2, 6})); System.out.println(minSumNonAdjNonEnd(new int[] {2, 2, 3, 2})); 5 4 4 3 Exception in thread "main" java.lang.IllegalArgumentException: impossible

Aquí hay una implementación javascript en vivo de un algoritmo que:

  • encuentra los 4 elementos más pequeños (excluyendo el primer / último elemento de la búsqueda)
  • encuentra los pares de estos 4 elementos que no son adyacentes en la matriz original
  • Encuentra de estos pares el que tiene la suma mínima.

function findMinNonAdjacentPair(a) { var mins = []; // quick exits: if (a.length < 5) return {error: "no solution, too few elements."}; if (a.some(isNaN)) return {error: "non-numeric values given."}; // collect 4 smallest values by their indexes for (var i = 1; i < a.length - 1; i++) { // O(n) if (mins.length < 4 || a[i] < a[mins[3]]) { // need to keep record of this element in sorted list of 4 elements for (var j = Math.min(mins.length - 1, 2); j >= 0; j--) { // O(1) if (a[i] >= a[mins[j]]) break; mins[j+1] = mins[j]; } mins[j+1] = i; } } // mins now has the indexes to the 4 smallest values // Find the smallest sum var result = { sum: a[mins[mins.length-1]]*2+1 // large enough } for (var j = 0; j < mins.length-1; j++) { // O(1) for (var k = j + 1; k < mins.length; k++) { if (Math.abs(mins[j] - mins[k]) > 1) { // not adjacent if (result.sum > a[mins[j]]+a[mins[k]]) { result.sum = a[mins[j]]+a[mins[k]]; result.index1 = mins[j]; result.index2 = mins[k]; }; if (k < j + 3) return result; // cannot be improved break; // exit inner loop: it cannot bring improvement } } } return result; } // Get I/O elements var input = document.getElementById(''in''); var output = document.getElementById(''out''); var select = document.getElementById(''pre''); function process() { // translate input to array of numbers var a = input.value.split('','').map(Number); // call main function and display returned value output.textContent = JSON.stringify(findMinNonAdjacentPair(a), null, 4); } // respond to selection from list select.onchange = function() { input.value = select.value; process(); } // respond to change in input box input.oninput = process; // and produce result upon load: process();

Type comma-separated list of values (or select one):</br> <input id="in" value="2, 2, 1, 2, 4, 2, 6"> &lt;= <select id="pre"> <option value="5, 2, 4, 6, 3, 7">5, 2, 4, 6, 3, 7</option> <option value="1, 2, 3, 3, 2, 1">1, 2, 3, 3, 2, 1</option> <option value="4, 2, 1, 2, 4">4, 2, 1, 2, 4</option> <option value="2, 2, 1, 2, 4, 2, 6" selected>2, 2, 1, 2, 4, 2, 6</option> </select> </br> Output:</br> <pre id="out"></pre>

El algoritmo tiene algunos bucles con las siguientes complejidades de gran O:

  • encuentre 4 valores más pequeños: O (n) , ya que el bucle interno se ejecuta como máximo 3 veces, que es O (1)
  • La suma más pequeña de pares no adyacentes tiene un bucle doble: en total, el cuerpo funcionará a lo sumo 4 veces = O (1) . NB: El número de pares posibles es 6, pero se garantiza que la ejecución saldrá de los bucles antes.

Entonces el algoritmo se ejecuta en O (n) .

Creo que esto debería funcionar:

Encuentra el elemento mínimo 3 y sus índices. Ya que todos ellos no pueden ser adyacentes, elige 2 entre ellos.

Si todos ellos son adyacentes y el número mínimo está en el medio de ellos, itere a través de todos los elementos, encuentre el cuarto elemento mínimo, elija el mínimo de min1+min4 , min2+min3 , el que sea más pequeño.

También puedes hacer esto en una iteración.

Creo que esto no necesita ningún razonamiento profundo, y se puede resolver en una sola pasada, manteniendo la solución óptima de los elementos de matriz procesados ​​hasta el momento:

public static int[] minimumSumOfNonAcjacentElements(int[] a) { // the result for the sequence a[1:i] int minSum = Integer.MAX_VALUE; int minSumElement1 = Integer.MAX_VALUE; int minSumElement2 = Integer.MAX_VALUE; // the minimum element eligible for joining with a[i], i.e. from a[1 : i-2] int minElement = a[1]; int prevElement = a[2]; // a[i - 1] for (int i = 3; i + 1 < a.length; i++) { int sum = minElement + a[i]; if (sum < minSum) { minSum = sum; minSumElement1 = minElement; minSumElement2 = a[i]; } if (prevElement < minElement) { minElement = prevElement; } prevElement = a[i]; } return new int[] {minSumElement1, minSumElement2}; }

Aquí hay un código de prueba, con los casos de la esquina de la pregunta de OP:

private static void test(int minSumIndex1, int minSumIndex2, int... input) { int[] result = minimumSumOfNonAcjacentElements(input); if (result[0] == minSumIndex1 && result[1] == minSumIndex2) { // ok } else { throw new AssertionError("Expected: " + minSumIndex1 + ", " + minSumIndex2 + ". Actual=" + Arrays.toString(result)); } } public static void main(String[] args) throws Exception { test(2, 2, 4, 2, 1, 2, 4); test(1, 2, 2, 2, 1, 2, 4, 2, 6); test(1, 2, 0, 2, 1, 2, 4, 2, 0); System.out.println("All tests passed."); }

Edición: tienes razón, ignoré completamente la restricción de adyacencia. Por suerte he pensado en una solución. El algoritmo va así:

  1. Se ejecuta una vez sobre la matriz para encontrar el más pequeño (O(n))
  2. Corres por segunda vez para encontrar el segundo más pequeño (O(n))
  3. Si el segundo más pequeño no es adyacente al más pequeño, hemos terminado ( O(1) , solo una comprobación de índice)
  4. De lo contrario, ejecute una tercera vez para encontrar la tercera más pequeña (aún O(n) )
  5. Si no es adyacente a la devolución más pequeña, la más pequeña y la tercera más pequeña, de lo contrario, el segundo y el tercero más pequeños

Encuentra los cuatro más pequeños y considera todas las posibilidades entre esos cuatro. El más pequeño no está adyacente a al menos uno de los segundos, terceros o cuartos más pequeños; la única otra posibilidad que podría ser mejor es la segunda y la tercera más pequeñas (suponiendo que no sean adyacentes).

He utilizado la programación dinámica para resolverlo.

La idea es crear primero la matriz que rastrea el mínimo encontrado hasta ahora como se muestra a continuación: Matriz de entrada = [1, 3, 0, 5, 6] Matriz mínima = [1, 1, 0, 0, 0]

Ahora, utilizando la matriz mínima y la matriz de entrada, podemos utilizar a continuación:

DP[i] = min(DP[i-1], min(first_data, second_data))

donde DP[i] significa el mínimo encontrado hasta ahora, que es la suma de dos elementos alternativos anteriores.

first_data = suma del elemento current en la matriz de entrada + suma del elemento current-2 en la matriz mínima

second_data = suma del elemento current-1 en la matriz de entrada + suma del elemento current-3 en la matriz mínima

import random def get_min(numbers): #disregard the first and last element numbers = numbers[1:len(numbers)-1] #for remembering the past results DP = [0]*len(numbers) #for keeping track of minimum till now found table = [0]*len(numbers) high_number = 1 << 30 min_number = numbers[0] table[0] = min_number for i in range(0, len(numbers)): DP[i] = high_number for i in range(1, len(numbers)): if numbers[i] < min_number: min_number = numbers[i] table[i] = numbers[i] else: table[i] = min_number for i in range(0, len(numbers)): min_first, min_second = high_number, high_number if i >= 2: min_first = numbers[i] + table[i-2] if i >= 3: min_second = numbers[i-1] + table[i-3] if i >= 1: DP[i] = min(min(DP[i-1], min_first), min_second) return DP[len(numbers)-1] input = random.sample(range(100), 10) print(input) print(get_min(input))

No sé si mi solución es correcta porque simplemente la probé con los datos en el OP, y ni siquiera sé si esto es mejor o peor que las otras ideas, pero quería intentarlo.

static void printMinimalSum(int[] A) { // Looking for mins so we init this with max value int[] mins = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE}; // Indices, used just to print the solution int[] indices = new int[]{-1, -1, -1}; // If the array has length 5 then there''s only one solution with the 2nd and 4th elements if (A.length == 5) { mins[0] = A[1]; indices[0] = 1; mins[1] = A[3]; indices[1] = 3; } else { // Loop on the array without considering the first and the last element for (int i = 1; i < A.length - 1; i++) { // We consider each element which is smaller than its neighbours if ((i == 1 && A[i] < A[i + 1]) // 1: first element, compare it with the second one || (i == A.length - 2 && A[i] < A[i - 1]) // 2: last element, compare it with the previous one || (A[i] < A[i + 1] && A[i] < A[i - 1])) { // 3: mid element, compare it with both neighbors // If the element is "legal" then we see if it''s smaller than the 3 already saved if (A[i] < mins[0]) { mins[0] = A[i]; indices[0] = i; } else if (A[i] < mins[1]) { mins[1] = A[i]; indices[1] = i; } else if (A[i] < mins[2]) { mins[2] = A[i]; indices[2] = i; } } } } // Compute the 3 sums between those 3 elements int[] sums = new int[]{Math.abs(mins[0]+mins[1]), Math.abs(mins[0]+mins[2]), Math.abs(mins[1]+mins[2])}; // Find the smaller sum and print it if (sums[0] < sums[1] || sums[0] < sums[2]){ System.out.println("Sum = " + sums[0] + " (elements = {" + mins[0] + "," + mins[1] + "}, indices = {" + indices[0] + "," + indices[1] + "}"); } else if (sums[1] < sums[0] || sums[1] < sums[2]){ System.out.println("Sum = " + sums[1] + " (elements = {" + mins[0] + "," + mins[2] + "}, indices = {" + indices[0] + "," + indices[2] + "}"); } else { System.out.println("Sum = " + sums[2] + " (elements = {" + mins[1] + "," + mins[2] + "}, indices = {" + indices[1] + "," + indices[2] + "}"); } } public static void main(String[] args) { printMinimalSum(new int[]{5, 2, 4, 6, 3, 7}); printMinimalSum(new int[]{1, 2, 3, 3, 2, 1}); printMinimalSum(new int[]{4, 2, 1, 2, 4}); printMinimalSum(new int[]{2, 2, 1, 2, 4, 2, 6}); }

La salida es:

Sum = 5 (elements = {2,3}, indices = {1,4} Sum = 4 (elements = {2,2}, indices = {1,4} Sum = 4 (elements = {2,2}, indices = {1,3} Sum = 3 (elements = {1,2}, indices = {2,5}

que parece bien

Qué hay de eso: encuentras k números más pequeños (o más precisamente sus índices) ( k suficientemente grande, digamos 10 ). Es seguro, que la pareja deseada está entre ellos. Ahora solo tiene que marcar los 50 pares posibles y seleccionar el mejor que satisfaga las restricciones.

No necesitas 10 , menos lo harías, pero más de 3 :)

Edición: encontrar k números más pequeños es O(n) , porque solo se guardan los 10 mejores, por ejemplo, en un montón (agregar nuevo elemento, eliminar el máximo O(k*logk)=O(1) operaciones).

Luego habrá un par que satisfaga las restricciones (no uno al lado del otro). También está claro que, si construyes la suma con un elemento que no sea de esos k , sería más grande que el mejor par elegido de esos k elementos.

La verificación en la mayoría de los pares k*k también es O(1) , por lo que todo el tiempo de ejecución es O(n) .

Utilizar la programación dinámica.

  1. Quite o ignore los primeros y últimos elementos de su matriz. Como no pueden participar en la solución, no son importantes. Una vez que haya hecho esto, también puede ignorar la restricción "no debe ser el primer o el último elemento", ya que ya lo hemos tenido en cuenta.
  2. Encuentre la solución para los primeros tres elementos de (lo que queda de) la matriz (y sin tener en cuenta la regla "sin primer / último elemento"). En este caso, solo hay una solución ( array[0] + array[2] ), por lo que este es un paso trivial.
  3. Memorice el elemento mínimo que no es el último elemento (es decir, min(array[0], array[1]) ).
  4. Encuentra la solución para los primeros cuatro elementos. No tenemos que rehacer todo el problema; en cambio, solo tenemos que preguntarnos si introducir el cuarto elemento nos permite producir una solución más pequeña. Podemos hacer esto agregando el cuarto elemento al elemento mínimo que memorizamos en el paso anterior y comparando la suma con la solución que encontramos en el segundo paso.
  5. Actualice el elemento mínimo memoized para que sea el mínimo de los tres primeros elementos.
  6. Continúe ampliando y actualizando de esta manera hasta que hayamos considerado toda la matriz.

Todo el algoritmo es O (n), ya que tanto la ampliación como la actualización son operaciones de tiempo constante. El algoritmo puede demostrarse correcto por simple inducción. O (n) también es un límite inferior ya que tenemos que considerar cada elemento de la matriz, por lo que este algoritmo es óptimo.