帶O（n）的算法以查找子集中三元產品的最小值和最大值

問題是如果給定數組數組，可以找到可形成的最小和最大三元產品（3個數的乘積）。我設法弄出了一個完美的代碼，但它的複雜性已經達到了(N^2)。如果可能，我需要一些幫助將其減少到O(N)。帶O（n）的算法以查找子集中三元產品的最小值和最大值

編輯：數字可以是正數也可以是負數。

這裏是我的代碼：

import java.util.*; 

class Result { 

    public static int min =50000000; 
    public static int max =-50000000; 

    public static int solve(int pos, int currPro, int depth) { 
      if (depth==3){ 
       check(currPro); 
      } 
      else { 
       for (int i=1; i<=Triplet.data.length-pos; i++){ 
       if(pos+i < Triplet.data.length){ 
        solve(pos+i,currPro*Triplet.data[pos+i],depth+1); 
       } 
      } 
     } 
     return 0; 
    } 

    public static void check(int currPro) { 
     if (currPro > max){ 
      max = currPro; 
     } 

     if (currPro < min){ 
      min = currPro; 
     } 
    } 
} 

class Triplet { 

    static int[] data; 

    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int num = sc.nextInt(); //Number of int 
     data = new int[num]; 
     for (int i=0;i<num;i++){ 
      data[i] = sc.nextInt(); 
     } 
     if (num==3){ 
      int result= data[0]*data[1]*data[2]; 
      System.out.println(""+result+" "+result); 
     } 
     else{ 
      Result.solve(-1, 1, 0); 
      System.out.println(""+Result.min+" "+Result.max); 
     } 
    } 
}

來源

2014-10-28 javabeginner_0101

可以在任何的數字是負數？如果他們都是積極的，看起來你可以通過找到最大的三個數字來獲得最大的產品。如果他們可能是負面的，你仍然應該能夠調整 - 找到最大的三個，找到最小的三個，然後如果兩個最小的三個都是負數，你將不得不嘗試一些情況，乘以兩個負數和一個正數。 – ajb 2014-10-28 03:00:34

你將無法達到線性時間。線性時間意味着一次通過數組以找到您的值。在這種情況下，我不認爲這是可能的，除非是巧合。 – 2014-10-28 04:44:35

@TylerWeaver：不，在線性時間內做到這一點非常簡單。 – tmyklebu 2014-10-28 05:04:06

試試這個

在O（N）時間找到最小的三個和三個數最多（無論陰性或陽性者）與快速排序的分區。
將您的O（N^2）解法應用於6個數字的數組。

運行時間 - O（N）

來源

2014-10-28 04:55:04

帶O（n）的算法以查找子集中三元產品的最小值和最大值

回答

相關問題