Necesito escribir un programa para encontrar el producto Max de tres números para una matriz dada de tamaño N. ¿Hay algún algoritmo efectivo para esto? Solo necesito saber los pasos del algoritmo. No de algoritmos que pensé que funciona para todos los casos de prueba. Gracias! FYI La matriz puede contener + ve, -ve, o cero elementos)Producto máximo de los tres números para una matriz de tamaño dada N
Encuentra los tres números más grandes en la matriz (n1, n2, n3) y los dos números más pequeños (m1, m2).
La respuesta es o bien n1 x n2 x n3 o n1 x m1 x m2
Dada una matriz de list = (n1, n2, n3, ...). Puedes hacer esto en 3 pases.
Let a1 = max (|n_i|)
Let a2 = max (|n_i|) where n_i != a1
Ahora a1 * a2 es positivo, negativo o cero. Si es cero, entonces hay muchas soluciones; elige cualquier n_i del resto de los números. Si a1 * a2> 0, elija el número positivo más grande, de lo contrario, el número negativo más pequeño. Más sucintamente, puede simplemente hacer una pasada por el resto de la lista:
Let max_product = max (a1*a2*n_i) where n_i != a1 or a2
El método de obtener el producto máximo de 3 consiste básicamente en encontrar los mayores 3 números de la matriz y los 2 números más pequeños de la matriz en solo 1 iteración sobre la matriz. Por supuesto hay una gran variedad de soluciones, pero esta es la óptima 1 porque el tiempo para resolver el problema es O (n), el tiempo de otras soluciones es O (n lg n)
Aquí está el código java: por cierto, hay una garantía de que la matriz de entrada no está vacía y contiene un mínimo de 3 elementos, por lo que no es necesario realizar comprobaciones adicionales para vacíos, etc.
int solution(int[] a) {
/* los mínimos inicializa con int max para evitar casos con max extrema en la matriz y las falsas mínimas 0 mínimos devueltos */
int min1 = Integer.MAX_VALUE;
int min2 = Entero.VALOR MÁXIMO;
/* la misma lógica para inicializaciones máximos pero por supuesto invertida para evitar valores mínimos extremos en matriz y falsos 0 máximos */
int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int max3 = Integer.MIN_VALUE;
// la iteración sobre la matriz
for (int i = 0; i < a.length; i++) {
// prueba si max1 es más pequeño que el valor actual de la matriz
if (a[i] > max1) {
/* store the m AX1 valor actual en un var temp para probarlo más tarde contra el segundo máximo aquí como se puede ver es una cadena de cambios si se cambia el mayor máximo hay que cambiar a la otra 2 */
int tempMax1 = max1;
// asigna el valor de la matriz actual como máximo valor anterior max1
max1=a[i];
// test tempMax1 contra max2
if(tempMax1>max2){
/* valor max2 tienda en valor tempMax2 para probarlo ag MAX3 ainst y asignarla a un máximo de 3 si es más grande */
int tempMax2 = max2;
max2 =tempMax1;
if(tempMax2>max3){
max3 = tempMax2;
}
/* prueba para ver si tempMax1 es más grande si no es más grande que MAX3, esto sucede cuando max1 consigue un nuevo valor y el viejo valor de max1 es igual con Max2 pero más grande que MAX3 */
}else{
if(tempMax1>max3){
max3 = tempMax1;
}
}
/* en caso de que si la corriente a [i] no es más grande que max1 lo probamos a ver quizá es más grande que la segunda máx. A continuación, se aplica la misma lógica desde arriba aquí para MAX3 */
}else if(a[i]>max2){
int tempMax2 = max2;
max2 = a[i];
if(tempMax2>max3){
max3 =tempMax2;
}
/* si finalmente valor de matriz actual no es más grande que max1 y max2 quizá es mayor que MAX3 */
}else if(a[i]>max3){
max3 = a[i];
}
/* La lógica de arriba con máximos se aplica aquí con mínimos pero, por supuesto, se invierte a para descubrir los 2 mínimos de la matriz actual. */
if (a[i] < min1) {
int tempMin1 = min1;
min1 = a[i];
if (tempMin1 < min2) {
min2 = tempMin1;
}
} else if (a[i] < min2) {
min2 = a[i];
}
}
/* después de descubrir los 3 más grandes máximos y los mínimos 2 más pequeñas de la matriz hacemos los 2 productos de 3 desde el mayor máximo y las 2 mínimos. Esto es necesario porque matemáticamente el producto de 2 valores negativos es un valor positivo, y debido a este producto de min1 * min2 * max1 puede ser mayor que max1 * max2 * max3 y el producto construido a partir de los 3 máximos.*/
int prod1 = min1 * min2 * max1;
int prod2 = max1 * max2 * max3;
// aquí simplemente devolvemos el producto más grande
return prod1 > prod2 ? prod1 : prod2;
}
Ésta es una buena solución en Java:
class Solution {
public int solution(int[] A) {
int result1, result2;
Arrays.sort(A);
result1 = A[0] * A[1] * A[A.length-1];
result2 = A[A.length-1] * A[A.length-2] * A[A.length-3];
if (result1 >= result2) return result1;
else return result2;
}
}
No es una solución eficiente, pero una copia de seguridad útil mostrar el uso de estructuras de datos. Crea un montón máximo y mínimo de estos enteros. A continuación, elimine la raíz del montón máximo hasta que obtenga 3 enteros distintos (top 3) y obtenga los dos enteros distintos del montón mínimo. El resto de los controles como se ha mencionado en otras respuestas Max (max1 * * max2 MAX3, max1, min-1, Min2)
def max_three_product(a):
a=sorted(a)
max_prod=a[-1]*a[-2]*a[-3]
if a[0]>0:
return a[-1]*a[-2]*a[-3]
else:
if a[0]*a[1]<0:
return max_prod
elif a[1]*a[2]>0:
if a[0]*a[1]*a[-1]>max_prod:
return a[0]*a[1]*a[-1]
else:
return max_prod
else:
if a[0]*a[1]*a[-1]>max_prod:
return a[0]*a[1]*a[-1]
else:
return max_prod
Agregue una explicación a su código. El código simplemente no es una respuesta útil. –
Aunque este código puede ayudar a resolver el problema, proporcionando contexto adicional con respecto a _por qué_ y/o _how_ responde la pregunta mejoraría significativamente su valor a largo plazo. Por favor, [edite] su respuesta para agregar una explicación, incluidas las limitaciones y suposiciones de . –
Escribí esta solución simple en Python, que yo estaba buscando y could't encontrar.
def ThreeHighestNumbers(arrayOfNumbers):
PmaxNum1 = 0
PmaxNum2 = 0
PmaxNum3 = 0
NMinNum1 = 0
NMinNum2 = 0
maxNumber = 0
for num in arrayOfNumbers:
if num < 0:
if num < NMinNum1:
NMinNum2 = NMinNum1
NMinNum1 = num
elif num < NMinNum2:
NMinNum2 = num
else:
if num > PmaxNum1:
PmaxNum3 = PmaxNum2
PmaxNum2 = PmaxNum1
PmaxNum1 = num
elif num > PmaxNum2:
PmaxNum3 = PmaxNum2
PmaxNum2 = num
elif num > PmaxNum3:
PmaxNum3 = num
maxNumber = PmaxNum1 * PmaxNum2 * PmaxNum3
if maxNumber == 0:
return []
if maxNumber < PmaxNum1 * NMinNum1 * NMinNum2:
return [PmaxNum1,NMinNum2,NMinNum1]
else:
return [PmaxNum1,PmaxNum2,PmaxNum3]
arraOfNumbers = [1,2,3,4,5,6,-8,-9,0]
print ThreeHighestNumbers(arraOfNumbers)
Utilice un procedimiento BubbleSort y divídalo en tres iteraciones. Tome la parte inferior de tres y multiplique. Eso debería proporcionarte la solución.
int count = 0, j=a.length;
boolean swap = false;
do
{
swap = false;
for(int i=1;i<j;i++)
{
if(a[i]<a[i-1])
{
int t= a[i];
a[i] = a[i-1];
a[i-1] = t;
swap = true;
}
}
System.out.println(j+" Iteration:"+Arrays.toString(a));
j--;
if(swap)
count++;
} while(swap && count<3);
System.out.println(Arrays.toString(a));
return a[a.length-1]*a[a.length-2]*a[a.length-3];
¿Por qué no es solo n1 x n2 x n3? –
@ Ink-Jet porque m1 y m2 pueden ser números negativos grandes – mob
Excluyendo 0, por supuesto :) –