對於給定數組大小爲N的三個數的最大乘積

Question

我需要編寫一個程序來查找給定數組大小爲N的三個數的最大乘積。 有沒有對此有效的算法？ 我只需要知道算法步驟。非我認爲適用於所有測試用例的算法。 謝謝！ FYI數組可包含+ ve，-ve或零元素）

Answer 1

查找數組中的三個最大數字（n1，n2，n3）和兩個最小數字（m1，m2）。

答案是要麼N1 X N2 N3 X或N1 X M1 X平方米

Answer 2

給定列表的陣列=（N1，N2，N3 ...）。你可以通過3次。

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

現在a1 * a2是正數，負數或零。如果爲零，那麼有很多解決方案;從其餘的數字中挑選任何n_i。如果a1 * a2> 0，則選擇最大的正數，否則選擇最小的負數。更簡潔地說，你可以做一次通過列表的其餘部分：

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

Answer 3

的方法得到的3最大的產品包括在基本找到該數組中最大的3個號碼，最小的2號從數組在數組中只需要1次迭代。當然有很多種解決方案，但這是最優的1，因爲解決問題的時間是O（n），其他解決方案時間是O（n lg n）

這裏是java代碼： 順便說一句，有一個保證，輸入數組是非空的，並且包含最少3個元素，所以不需要額外檢查空等等。

int solution(int[] a) { 

/*與最大INT初始化以避免在陣列和假量滴極端最大值情況下，最小值0最小值返回*/

INT MIN1 = Integer.MAX_VALUE的;

int min2 =整數。MAX_VALUE;

/*爲最大初始化但當然反轉，以避免在陣列極端最低值的相同的邏輯和假0最大值*/

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

//迭代陣列之上

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

//測試max1是否小於當前數組值

 if (a[i] > max1) { 

/*存儲m在一個臨時的無功電流AX1值來測試它後來對第二最大 在這裏，你可以看到的是變化的鏈條，如果改變了我們必須改變，另2 */

  int tempMax1 = max1; 

//分配最大最大當前數組值作爲針對MAX2最大值

  max1=a[i]; 

//測試tempMax1前MAX1值

  if(tempMax1>max2){ 

/*存儲在MAX2值tempMax2值來測試它AG如果它是更大的ainst MAX3並將其分配給最多3 */

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

/*測試，看看tempMax1較大，如果不大於MAX3大，當 MAX1得到一個新值與舊這種情況正在發生MAX1的值等於與MAX2但大於MAX3 */

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

在殼體/ *如果當前一個[i]爲不大於MAX1更大我們進行測試，看看也許比第二 最大值更大。然後，從上述相同的邏輯，這裏應用於MAX3 */

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

/*最後如果當前數組值不大於MAX1和MAX2大也許比MAX3更大*/

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

/*上面的邏輯與最大值是在這裏應用最小值，但當然反轉到 發現當前數組的2個最小值。 */

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

/*後，我們發現從陣列 3個最大的最大值和2個最小的最小值，我們做了2個產品3從最大的最大值和最小值2。這是必要的 ，因爲在數學上2個負值的乘積是正值，並且因爲min1 * min2 * max1的乘積可以大於max1 * max2 * max3 以及由3個最大值構建的乘積。*/

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

//這裏我們只返回最大的產品

return prod1 > prod2 ? prod1 : prod2; 

} 

Answer 4

這是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

不是一個有效的解決方案，但一個有用的備份顯示數據結構的使用。從這些整數中創建一個最大堆和最小堆。然後從max堆中刪除根，直到獲得3個不同的整數（前3），並從min堆中獲取至少兩個不同的整數。做檢查的其餘部分作爲最大其他應答（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

提到我寫在Python這種簡單的解決方案，我一直在尋找和發現便無法。

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

請使用BubbleSort過程並在三次迭代中中斷。取三個的底部並乘。這應該爲您提供解決方案。

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