從矩陣中找到所有局部最大值

-6

請在Java中編寫一個方法，它將接收一個矩陣（int [] []矩陣）作爲輸入並且應該從矩陣中找到所有局部最大值。矩陣中的局部最大值是一個比所有直接鄰居都大的數字。該方法應返回找到的所有本地最大號碼的位置列表。從矩陣中找到所有局部最大值

我想這代碼，以使這一點，但不知道這種想法是正確與否的代碼

private static List<Integer> findLocal(int[][] matrix) 
{ 

    List<Integer> locals = new ArrayList<Integer>(); 

    for (int i = 0; i < matrix.length; i++) { 
     for (int j = 0; j < matrix[0].length; j++) { 

      if (i < matrix.length - 1 && j < matrix[0].length - 1) { 
       if (matrix[i][j] < matrix[i + 1][j] && matrix[i][j] < matrix[i][j + 1] && matrix[i][j] < matrix[i + 1][j + 1]) { 
        locals.add(i + j); 
       } else { 

       } 

      } 
     } 

    } 

    return locals; 
}

來源

2011-08-22 ali mohammed

你有什麼試過？這個算法的哪一部分你覺得困難？我們不會只爲你編碼;我們在這裏*幫助*。 – dlev

聽起來像功課。你到目前爲止嘗試過哪些具體問題？ – flolo

也許他不知道在哪裏或如何開始？ – mort

好了，現在看來你也來一個想法了，它基本上是一個工作的想法。（i，j），（i，j + 1），（von Neumann）鄰居是（i + 1，j）（i-1，j）和（i，j-1）。

因此，當你檢查這一點時，它應該在一般的工作，但是：你必須特別照顧的邊界。由於當你在那裏時沒有第-1列和第n + 1列/行，因此不考慮鄰居點。你如何處理它，取決於你想要如何處理它：如果鄰里環繞，如果邊界具有恆定的值，是否應該將其視爲-infty？

來源

2011-08-22 08:13:42 flolo

+1我忘了邊界的事情！ –

你寫

if (matrix[i][j] < matrix[i + 1][j] 
    && matrix[i][j] < matrix[i][j + 1] 
    && matrix[i][j] < matrix[i + 1][j + 1]) {

其檢查元素是否超過三個鄰國的更小。其他五個鄰居呢？讓我們來看看它們：

if (matrix[i][j] < matrix[i + 1][j] 
    && matrix[i][j] < matrix[i+1][j-1] 
    && matrix[i][j] < matrix[i+1][j+1] 
    && matrix[i][j] < matrix[i][j + 1] 
    && matrix[i][j] < matrix[i][j - 1] 
    && matrix[i][j] < matrix[i-1][j-1]) 
    && matrix[i][j] < matrix[i-1][j]) 
    && matrix[i][j] < matrix[i-1][j+1]) {

這假設你想檢查元素的8個直接鄰居，即直線和對角線。如果這不是你想要的，請調整。

另外要求是找到當地的最大值。這確定了當地的最低標準。將<更改爲>。

另一件事是locals.add(i + j)不會做你認爲它做的事。如果元素（i = 3，j = 4）是一個局部最大值，那麼你的意思是locals.add(7)，這顯然不是你想要的。

來源

2011-08-22 08:13:59

你拿摩爾鄰居 - 不知道什麼原始海報想要的 - 我使用馮諾依曼，因爲它更短（我懶惰;-)。 +1我沒有看到錯誤的關係 – flolo

您必須分別存儲i和j才能正確記住元素的位置。因此，

List<Integer> locals = new ArrayList<Integer>();

將不起作用。您可以使用

List<Integer[]> locals = new ArrayList<Integer[]>();

改爲。並添加一個新發現的局部最大的位置，使用

Integer[] localMax = {i, j}; 
locals.add(localMax);

來源

2011-08-22 08:15:40 mort

我認爲沒有必要爲每一個矩陣元件8個比較。你應該採取兩個額外的數組：

MATRIX[n+2][n+2]：它將包含YOUT輸入矩陣有一個額外的層的所有INT_MIN的（所以，每一個矩陣元素具有所有8個鄰居）。
Mark[n+2][n+2] = {0}（你應該只需要訪問的元素在沒有標記輸入矩陣）如果一個矩陣元素被聲明爲當地最低，你應該標記所有在鄰居馬克[] [ ]矢量。

通過這樣做，複雜性依然爲O（n^2），但沒有。的比較將最小化。

來源

2011-09-01 06:13:43 Learner

從矩陣中找到所有局部最大值

回答

相關問題