Suchen Sie das höchste Produkt von drei Zahlen

Question

Angesichts einer Reihe von Ints, arrayofints, finden Sie das höchste Produkt, Highestproduct, können Sie von drei der ganzen Zahlen. Das Eingabearray von Ints wird immer mindestens drei Ganzzahlen haben.

Also habe ich drei Zahlen von arrayofints knallt und steckte sie in highestproduct:

Highestproduct = arrayofints[:2] 
for item in arrayofints[3:]: 
    If min(Highestproduct) < item: 
     Highestproduct[highestproduct.index(min(Highestproduct))] = item 

Wenn min von highestproduct weniger als Punkt: die niedrigste Zahl mit der aktuellen Nummer ersetzen.

Dies würde mit dem höchsten Produkt enden, aber anscheinend gibt es eine bessere Lösung. Was ist los mit meinem Ansatz? Wäre meine Lösung O (n)?

Answer 1

Behalten Sie die zwei minimalen Elemente und die drei maximalen Elemente im Auge. Die Antwort sollte min1 * min2 * max1 oder max1 * max2 * max3 lauten.

Um das maximale Produkt von 3 Zoll zu erhalten, müssen wir 3 maximale Elemente wählen. Allerdings gibt es einen Haken, dass wir 2 der kleinsten 3 Max Elemente mit den 2 Min Bits ersetzen können. Wenn beide kleinsten Eingänge negativ sind, ist ihr Produkt positiv, so dass min1 * min2 möglicherweise größer als max2 * max3 ist (wobei max2 und max3 2 der kleinsten von 3 max Elementen aus dem Array sind).

Dies läuft in O(n) Zeit.

Answer 2

Es gibt einige Fänge zu diesem Problem, in einer Liste, die sowohl positive als auch negative int enthält, könnte die größte Kombination der kleinste negative, der zweitkleinste negative Wert, der größte positive Wert oder der größte positive Wert, der zweitgrößte positive Wert und der dritte sein größter Wert;

Zum Beispiel sollte eine Liste von -5,-1,1,2,3 15 zurückgeben, aber wenn es nur negative Werte in der Liste gibt, funktioniert das nicht, anstatt die kleinsten negativen ganzen Zahlen auszuwählen, ist die große Kombination tatsächlich die drei größten negativen Werte. Zum Beispiel: -5,-4,-3,-2,-1 sollte -6 zurückgeben. Der einfachste Weg, dies zu kodieren, wäre einfach die drei größten positiven Werte zu speichern (0 als positiv zu betrachten),

Drei kleinste negative Werte und drei größte negative Werte, während wir durch das Array gehen, dann versuchen wir alle Kombinationen davon neun Zahlen und bekommen die max. Dies dauert nur O(n) Zeit und O(1) Platz.

Answer 3

Hier ist eine C++ Durchführung des Programms mit der Laufzeit von O (N):

#define size 5 
int A[size] = {5,4,5,10,-6}; 

int highest_product_of_3() 
{ 
    int highest = max(A[0],A[1]); 
    int lowest = min(A[0],A[1]); 

    int highestProductOf2 = A[0]*A[1]; 
    int lowestProductOf2 = A[0]*A[1]; 

    int highestProductOf3 = A[0]*A[1]*A[2]; 

    for (int i=2;i<size;i++) 
    { 
     int current = A[i]; 

     // Max of 3 values: 
     //     highest_product_of_3   OR 
     //     current*highestProductOf2  OR 
     //     current*lowestProductOf2 

     highestProductOf3 = max(max(highestProductOf3, current*highestProductOf2), 
           current*lowestProductOf2); 

     highestProductOf2 = max(max(highestProductOf2, current*highest), 
           current*lowest); 

     lowestProductOf2 = min(min(lowestProductOf2, current*highest), 
           current*lowest); 

     highest = max(highest, current);  // update highest 

     lowest = min(lowest, current);   // update lowest 
    } 


    return highestProductOf3; 
} 

Answer 4

Wenn Sie sortieren arrayofints ersten, der schlimmste Fall Zeit O(n log n) statt O(n) läuft (also nicht ganz so schnell). Aber der Code ist wirklich kurz. Und was ist ein bisschen log n zwischen Freunden überhaupt?

def highest_product(list_of_ints): 
    if len(list_of_ints) < 3: 
     return None 
    sorted_ints = sorted(list_of_ints) 
    return max(sorted_ints[0] * sorted_ints[1] * sorted_ints[-1], sorted_ints[-3] * sorted_ints[-2] * sorted_ints[-1]) 

(Um klar zu sein, Sortierung ausdrücklich die Notwendigkeit, den Überblick zu behalten den drei höchsten Zahlen, und die drei niedrigsten entfernt -. Diese sind eine Art artige Operationen sind aber billiger als die gesamte Liste Sortierung)