Prodotto massimo dei tre numeri per una determinata serie di dimensioni N

Question

Ho bisogno di scrivere un programma per trovare il prodotto Max di tre numeri per una data matrice di dimensioni N. Esiste un algoritmo efficace per questo? Ho solo bisogno di conoscere i passaggi dell'algoritmo. Non di algoritmi che pensavo funzionassero per tutti i casi di test. Grazie! L'array FYI può contenere + elementi ve, -ve o zero)

Answer 1

Trova i tre numeri più grandi nell'array (n1, n2, n3) e i due numeri più piccoli (m1, m2).

La risposta è sia n1 x n2 x n3 o n1 x m1 x m2

Answer 2

Dato un array di list = (n1, n2, n3 ...). Puoi farlo in 3 passaggi.

Let a1 = max (|n_i|) 
Let a2 = max (|n_i|) where n_i != a1 

Ora a1 * a2 è positivo, negativo o zero. Se zero allora ci sono molte soluzioni; scegli qualsiasi n_i dal resto dei numeri. Se a1 * a2> 0, seleziona il numero positivo più grande, altrimenti il ​​numero negativo più piccolo. Più sinteticamente, si può solo fare un passaggio attraverso il resto della lista:

Let max_product = max (a1*a2*n_i) where n_i != a1 or a2 

Answer 3

Il metodo ottenere il prodotto massimo di 3 consiste in sostanza trovare i più grandi 3 numeri dalla matrice e il più piccolo 2 numeri dalla matrice in solo 1 iterazione sull'array. Ci sono naturalmente una grande varietà di soluzioni, ma questo è il 1 ottimale perché il tempo per risolvere il problema è O (n), l'altra soluzione è O (n lg n)

Ecco il codice java: dal modo in cui vi è una garanzia che l'array di input non è vuoto e contiene almeno 3 elementi, quindi non c'è bisogno di controlli aggiuntivi per vuoto e così via.

int solution(int[] a) { 

/* minimi inizializzati con int max per evitare casi con estrema max a matrice e falsi minimi 0 minimi restituiti */

int = min1 Integer.MAX_VALUE;

int min2 = Numero intero.MAX_VALUE;

/* la stessa logica per inizializzazioni massimo ma ovviamente invertita per evitare valori minimi estremi a matrice e falsi 0 massimi */

int max1 = Integer.MIN_VALUE; 
    int max2 = Integer.MIN_VALUE; 
    int max3 = Integer.MIN_VALUE; 

// l'iterazione su matrice

for (int i = 0; i < a.length; i++) { 

// prova se max1 è minore del valore dell'array attuale

 if (a[i] > max1) { 

/* memorizzare il m ax1 valore corrente in una temperatura var per testare più tardi contro la seconda massima qui come si può vedere è una catena di cambiamenti se è cambiato il più grande massimo dobbiamo cambiare l'altro 2 */

  int tempMax1 = max1; 

// assegnare il valore della matrice corrente come massimo valore precedente max1

  max1=a[i]; 

// test tempMax1 contro max2

  if(tempMax1>max2){ 

/* memoria dei valori max2 valore tempMax2 provarlo ag max3 ainst e assegnarlo ad un massimo di 3, se è più grande */

   int tempMax2 = max2; 
       max2 =tempMax1; 
       if(tempMax2>max3){ 
        max3 = tempMax2; 
       } 

/* test per vedere se tempMax1 è più grande se non è più grande di max3, questo sta accadendo quando max1 ottiene un nuovo valore e il vecchio valore della max1 è uguale con Max2 ma più grande di max3 */

  }else{ 
       if(tempMax1>max3){ 
        max3 = tempMax1; 
       } 
      } 

/* nel caso in cui se la corrente a [i] non è più grande di max1 ci prova per vedere forse è più grande di seconda max. Poi la stessa logica di cui sopra si applica qui per max3 */

 }else if(a[i]>max2){ 
      int tempMax2 = max2; 
      max2 = a[i]; 
      if(tempMax2>max3){ 
       max3 =tempMax2; 
      } 

/* infine se il valore corrente di matrice non è più grande di max1 e max2 forse è superiore max3 */

 }else if(a[i]>max3){ 
      max3 = a[i]; 
     } 

/* La logica da sopra con i massimi è applicata qui con i minimi ma ovviamente invertita a scoprire i 2 minimi dall'array attuale. */

 if (a[i] < min1) { 
      int tempMin1 = min1; 
      min1 = a[i]; 
      if (tempMin1 < min2) { 
       min2 = tempMin1; 
      } 
     } else if (a[i] < min2) { 
      min2 = a[i]; 
     } 
    } 

/* dopo abbiamo scoperto le 3 più grandi massimi e minimi i 2 più piccoli dalla matrice facciamo i 2 prodotti 3 dal più grande al massimo e le 2 minimi. Questo è necessario perché matematicamente il prodotto di 2 valori negativi è un valore positivo, e a causa di questo prodotto di min1 * min2 * max1 può essere maggiore di max1 * max2 * max3 e il prodotto ricavato dai 3 massimi.*/

int prod1 = min1 * min2 * max1; 
    int prod2 = max1 * max2 * max3; 

// qui dobbiamo solo restituire il più grande prodotto

return prod1 > prod2 ? prod1 : prod2; 

} 

Answer 4

Questa è una buona soluzione in 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; 

    } 
} 

Answer 5

Non una soluzione efficiente, ma un sostegno utile a mostrare l'uso delle strutture dati. Crea un heap massimo e un heap minimo di questi numeri interi. Quindi elimina la radice dall'heap massimo finché non ottieni 3 interi distinti (top 3) e ottieni i due meno interi distinti dall'heap min. Il resto dei controlli Come detto in altre risposte max (max1 * * max2 max3, max1, min1, min2)

Answer 6

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 

Answer 7

ho scritto questa semplice soluzione in Python che stavo cercando e could't trovare.

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) 

Answer 8

Utilizzare una procedura BubbleSort e interrompere entro tre iterazioni. Prendi il fondo del tre e moltiplica. Questo dovrebbe darti la soluzione.

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];