如何從Hackerrank優化沙漏程序？

-1

這是可以在Hackerrank網站上找到的沙漏問題。如何從Hackerrank優化沙漏程序？

這是解決問題的鏈接：Hourglass

這裏是我寫的沙漏問題的代碼：

public class Solution 
    { 
    public static int hourglass(int[][] a, int n) 
    { 
     int max = -999; 
     for (int i = 0; i < n; i++) 
     {   
      for (int j = 0; j < n; j++) 
      { 
       int sum = 0; 
       boolean flag = false; 

       if ((i+2) < n && (j+2) < n) 
       { 
        sum += a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j+1] + a[i+2][j] + a[i+2][j+1] + a[i+2][j+2]; 
        flag = true; 
       } 
       if (sum > max && flag == true) 
        max = sum; 
      } 
     } 
     return max; 
    } 
    public static void main(String[] args) 
    { 
     Scanner scanner = new Scanner(System.in); 
     int n = 6; 
     int[][] a = new int[6][6]; 

     for (int i = 0; i < n; i++) 
      for (int j = 0; j < n; j++) 
       a[i][j] = scanner.nextInt(); 

     int maxSum = hourglass(a, n); 
     System.out.println(maxSum); 
    } 
}

我現在的問題

，上面的代碼編譯併成功運行，甚至通過了所有測試用例。但是，我的代碼需要O（n^2）個時間（這裏矩陣的大小是6，但是如果大小是n，那麼需要花費O（n^2）時間才能完成。）

需要O（n^2）時間來創建數組，並且我不關心。我感興趣的是優化沙漏（）方法，它需要O（n^2）時間來計算沙漏的總和。

那麼，有沒有辦法通過進一步優化來實現上述問題？

是否有可能在O（n）時間內解決問題？

實際上，我試圖通過刪除沙漏（）方法中的內部循環來解決O（n）時間中的問題，但它似乎不起作用。

P.S.我不需要一個工作代碼，我所需要的只是一些指向可能的改進（如果有的話）或最多的算法。

提前致謝！

來源

2017-08-01 doctorwho

我投票結束這個問題作爲題外話，因爲它屬於https://codereview.stackexchange.com/ – Andreas

我不要認爲這是可能的。你必須計算所有沙漏的總和。而沙漏的數量是'（n-2）^ 2'或'n^2-4n + 4'。這意味着沙漏的數量是O（n^2） –

@Andreas感謝您指出我應該在哪裏發佈我的代碼以供審閱。其實我很長一段時間都在尋找這樣的東西，因爲我有很多代碼需要審查。 – doctorwho

從技術上講，你的解決方案已經是O（n）。您將「n」定義爲二維數組的一邊，但如果您將n視爲您電路板上的唯一佈局，則n是行*列的組合。重新定義這種方式，你不能在這個問題上擊敗O（n）。

但是，您可以優化一些。你基本上是在6x6板上鋪設一個3x3的瓷磚。如果展示位置是由3x3圖塊的左上角定義的，那麼您將嘗試全部36個展示位置。如果你仔細想想，很多這些貼裝會讓你的瓷磚掛在電路板的邊緣。你真的只需要考慮前4x4職位而不是全部6x6職位。這仍然是一個O（n）的解決方案，但它會減少36次迭代降至16.

來源

2017-08-01 21:05:34 phatfingers

是的，我明白你的意思了！非常感謝......一個小而微妙的變化。當N值較大時，主要會影響性能。 – doctorwho

如何從Hackerrank優化沙漏程序？

回答

相關問題