尋找二維數組中的非空網格單元格

我有一個二維整數數組（例如1000乘1000），我們稱它爲矩陣。矩陣中的每個單元格都有一個X座標和Y座標（在本例中，每個單元從0到999）。最初，所有的網格單元具有0的值。在程序運行時間中，一些矩陣單元被設置爲另一個值<> 0尋找二維數組中的非空網格單元格

現在我需要一個快速功能（算法），需要一些X和Y值，並返回該座標處矩陣的值。但是，如果指定X/Y位置的矩陣爲0，那麼算法應該在矩陣內確定一個儘可能接近原始X/Y位置的非零值。

我曾經想過周圍，在每個循環週期增加抵消了原來的X/Y軸循環，但我不知道這是否真的是最快的算法...

任何想法？我寧願Java代碼，但任何僞代碼也很好:)

在此先感謝您的幫助！親切的問候，Matthias

來源

2011-09-08 Matthias

如果數組相對稀疏並且測試次數相對於插入數量較高，則幼稚方法可能需要很長時間。

另一種方法是構建一個空間分區樹，如四叉樹或k-d樹。最近鄰居搜索是以O（ln N）插入時間爲代價的O（ln N）。

來源

2011-09-08 16:22:34 Jimmy

如果您對矩陣的外觀沒有任何假設，您必須使用蠻力法來查看[X，Y]位置附近的所有值。

剛剛成立3×3平方米，在中心[X，Y]位置，並測試在廣場周邊
所有的值，如果你沒有找到非零值，只是繼續同方5×5， 7x7等，直到你找到一些東西。你必須處理大矩陣的邊界。

這只是一個循環，指數和適當的ifs的工作:-)沒有更快的算法，因爲你沒有任何信息，指南。

來源

2011-09-08 16:12:25 TMS

這取決於您希望包含多少行/列，以包含非0值。如果您希望1000x1000的網格具有<填充的100個位置，則應該在生成值時存儲列的非零值的信息。

如果那不是一種選擇，使用的財產以後這樣的：

public void foo() { 
    int[][]matrix = new int[1000][1000]; 
    int x = 0,y = 0; 
    if(matrix[x][y] != 0) return; 
    int min = 0, max=0; 
    boolean cont = true; 
    foreverloop: 
    while(cont) { 
     min--;max++; 
     for(int ii = min; ii < max; ii++) { 
      // secure that min and max dont exeed matrix here. 
      cont = false; 
      int[] higherEnd = Arrays.copyOf(matrix[ii], max); 
      int[] trunk = Arrays.copyOf(higherEnd, higherEnd.length-min); 
      Arrays.sort(trunk); 
      if(trunk[trunk.length-1] != 0) { 
       // HIT! we search this distance but no further. 
       trunk = Arrays.copyOf(higherEnd, higherEnd.length-min); 
       int source = trunk.length; 
       for(int distance = 0; ;distance++) { 
        if(source-distance>0) { 
         if(trunk[source-distance] != 0) { 
          // SCORE! 
          scoreHit(x+ii,y+source-distance); 
          break foreverloop; 
         } 
        } 
        if(source+distance<trunk.length) { 
         if(trunk[source+distance] != 0) { 
          // SCORE! 
          scoreHit(x+ii,y+source-distance); 
          break foreverloop; 
         } 
        } 
       } 
      } 
     } 
    } 
} 

public void scoreHit(int x, int y) { 
    // there could be several in nearly the same distances 
}

你可以優化是通過過濾掉你已經搜索領域，但我認爲這只是從X，Y更大的距離有所作爲

來源

2011-09-08 16:37:40

尋找二維數組中的非空網格單元格

回答

相關問題