Max Produkt der drei Zahlen für ein bestimmtes Array der Größe N

Question

Ich muss ein Programm schreiben, um das Max Produkt von drei Zahlen für ein gegebenes Array der Größe N zu finden. Gibt es einen effektiven Algorithmus dafür? Ich muss nur die Schritte des Algorithmus kennen. Nicht von Algorithmen, die ich dachte, funktioniert für alle Testfälle. Danke! FYI-Array darf + ve, -ve oder null Elemente enthalten)

Answer 1

Suchen Sie die drei größten Zahlen im Array (n1, n2, n3) und die zwei kleinsten Zahlen (m1, m2).

Die Antwort ist entweder n1 x n2 x n3 oder n1 x m1 x m2

Answer 2

eine Reihe von Liste Gegeben = (n1, n2, n3 ...). Sie können dies in 3 Durchgängen tun.

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

Nun ist a1 * a2 entweder positiv, negativ oder null. Wenn Null, dann gibt es viele Lösungen; Wählen Sie ein beliebiges n_i aus dem Rest der Zahlen. Wenn a1 * a2> 0, dann wähle die größte positive Zahl, ansonsten die kleinste negative Zahl. Kurz und bündig, können Sie nur einen Durchgang durch den Rest der Liste machen:

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

Answer 3

Das Verfahren besteht den max Produkt von 3 erhält grundsätzlich auf die größten drei Zahlen aus dem Array und die kleinsten 2 Zahlen aus dem Array finden in nur 1 Iteration über das Array. Es gibt natürlich eine große Vielzahl von Lösungen, aber dies ist die optimale 1, weil die Zeit, um das Problem zu lösen, ist O (n), die andere Lösungen ist 0 (0)

Hier ist der Java-Code: Übrigens gibt es eine Garantie, dass das Eingabe-Array nicht leer ist und mindestens 3 Elemente enthält, so dass keine zusätzlichen Prüfungen für leer usw. erforderlich sind.

int solution(int[] a) { 

/* die mit max initialisiert int Minima Fällen mit extremem max in Array und falsche minims zu vermeiden 0 Minimum zurück */

int min1 = Integer.MAX_VALUE;

int min2 = Ganze Zahl.MAX_WERT;

/* die gleiche Logik für maximale Initialisierungen aber natürlich invertiert extreme Minimalwerte in der Matrix zu vermeiden und false 0 Maxima */

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

// die Iteration über das Array

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

// test, wenn max1 kleiner als der aktuelle array-Wert ist

/* speichern Sie die m ax1 aktuellen Wert in einem temporären var es zu testen später gegen die zweite maximale hier, wie Sie ist eine Kette von Änderungen sehen können, wenn die größte max geändert wird, wir die andere 2 */

  int tempMax1 = max1; 

// zuweisen muss sich ändern das aktuelle Array Wert als maximale

  max1=a[i]; 

// test tempMax1 ehemaligen max1 Wert gegen max2

  if(tempMax1>max2){ 

/* store max2 Wert in tempMax2 Wert, den es zu testen ag ainst MAX3 und weist es max 3, wenn es größer ist */

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

/* Test, um zu sehen, ob tempMax1 größer ist, wenn nicht größer als MAX3 ist, dies geschieht, wenn max1 einen neuen Wert bekommt und die alten Wert max1 ist gleich mit max2 aber größer als MAX3 */

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

/* im Fall, wenn Strom a [i] nicht größer als max1 ist testen wir es vielleicht um zu sehen, ist größer als die zweite max. Dann wird die gleiche Logik von oben angelegt wird hier max3 */

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

/* schließlich, wenn die aktuelle Array-Wert nicht größer als max1 und max2 vielleicht größer ist als MAX3 */

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

/* Die Logik von oben mit Maxima wird hier mit Minima angewendet, aber natürlich invertiert auf , um die 2 Minima vom aktuellen Array zu entdecken. */

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

/*, nachdem wir die drei größten Maxima und die 2 kleinsten Minima aus dem Array wir tun, um die 2 Produkte von 3 aus dem größten Maximum und die 2 Minima entdeckt. Dies ist notwendig weil mathematisch das Produkt von 2 negativen Werten ist ein positiver Wert, und wegen das Produkt von min1 * min2 * max1 kann größer als max1 * max2 * max3 und das Produkt aus den 3 Maxima gebaut werden.*/

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

// hier kehren wir gerade das größte Produkt

return prod1 > prod2 ? prod1 : prod2; 

} 

Answer 4

Dies ist eine gute Lösung 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

keine effiziente Lösung, sondern eine sinnvolle Unterstützung zu zeige die Verwendung von Datenstrukturen. Erstellen Sie aus diesen Ganzzahlen einen Max-Heap und einen Min-Heap. Löschen Sie dann die Wurzel aus dem Max-Heap, bis Sie 3 verschiedene ganze Zahlen (Top 3) erhalten haben und die letzten zwei verschiedenen Integer aus dem Min-Heap erhalten haben. Haben Sie den Rest der Kontrollen, wie in anderen Antworten max erwähnt (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

Ich schrieb diese einfache Lösung in Python, die ich gesucht habe und could't zu finden.

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

Bitte verwenden Sie eine BubbleSort-Prozedur und brechen Sie innerhalb von drei Iterationen. Nimm den Grund von drei und multipliziere. Das sollte Ihnen die Lösung bieten.

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