¿Por qué es indeseable el método de “selección de selección”? Hay muchas cosas que podrías hacer; Sería útil saber lo que está tratando de evitar.
La forma más directa es hacer exactamente eso: tomar una pasada para identificar el elemento más grande y una segunda pasada para identificar el segundo elemento más grande. (El intercambio del elemento más grande al final de la matriz es opcional, pero facilita el salto en la segunda pasada).
La versión de un solo paso es generalmente más eficiente:
- ¿Cuál es la solución a este décimo problema polinómico de clase?
- ¿Cuál es el algoritmo para imprimir el alfabeto 'A' como patrón?
- ¿Qué es una cola prioritaria?
- ¿Hay algún algoritmo de aprendizaje automático para el que pones una línea y devuelve la línea más cercana en un conjunto de datos?
- ¿Los algoritmos están optimizados para discos duros normales * no * optimizados para unidades de estado sólido?
- Usaremos una variable L para contener el elemento “más grande” y otra variable N para contener el valor “próximo más grande”. Ponga el primer valor en la matriz en L, Ponga el segundo valor en la matriz en N. Intercambie N y L si N es mayor.
- Ahora, itere sobre el resto de la matriz, comparando cada valor con N.
- Si el elemento actual es mayor que N, reemplace el valor de N con el elemento de matriz actual. Luego verifique si N es ahora más grande que L, y si es así, cambie N y L.
Tenga en cuenta que, en el peor de los casos, hace tantas comparaciones como dos pases … pero la localidad de memoria es generalmente una victoria.
Otra opción es simplemente aplicar su rutina de clasificación favorita a la matriz (Quicksort, por ejemplo, o Timsort) y tomar los dos últimos elementos de la matriz.
Una opción bastante tonta es dividir y conquistar, que podría ser útil si desea paralelizar el problema (aunque la solución anterior se paraleliza muy bien).
Dados N elementos, calcula recursivamente el más grande y el siguiente más grande para el primer N / 2 y el segundo N / 2 de los elementos. Esto proporciona cuatro valores; utilizando la convención de nomenclatura presentada anteriormente, son: L1, N1, L2, N2.
Compare L1 con L2. El más grande es el mayor valor general. Supongamos que es L1. Entonces el siguiente valor más grande es max (L2, N1). En el caso donde el más grande es L2, entonces simétricamente el siguiente más grande es max (L1, N2). Entonces, en cada nivel de la recursión hacemos dos comparaciones.
El caso base de la recursión es solo uno o dos elementos. Si son dos, compárelos y devuelva el par (el más grande, el siguiente más grande). Si es un elemento, return (mayor, -infinito), un valor menor que cualquier entrada válida.
La recurrencia T (n) = 2T (n / 2) + 2 muestra que esta solución requiere solo comparaciones de O (n) también.
