2次元配列で空でないグリッドセルを見つける

Question

2次元の整数配列（1000で1000）を持っています。この行列の各セルには、X座標とY座標（この例ではそれぞれ0〜999）があります。最初にすべてのグリッドセルの値は0です。プログラム実行時には、マトリックスセルのいくつかが別の値<> 0に設定されています。XとYの値を取り戻す高速関数（アルゴリズム）が必要ですその座標における行列の値ただし、指定されたX/Y位置の行列が0である場合、アルゴリズムは行列内の可能な限り元のX/Y位置に近い非ゼロ値を決定する必要があります。

...

任意のアイデアを、私は、各ループサイクルでオフセットを増加させながら、元のX/Yの位置の周りにループについて考えているが、私はこれは本当に最速のアルゴリズムであるかどうかわかりませんか？私はJavaのコードを好むだろうが、任意の擬似コードも大丈夫です:)

あなたの助けを事前に感謝！ 種類Matthias

Answer 1

アレイが比較的まばらで、テストの数がインサートの数に比べて多い場合、素朴なアプローチは時間がかかる可能性があります。

代わりに、クォードツリーまたはk-dツリーなどの空間パーティションツリーを構築することもできます。最近傍探索は、O（ln N）挿入時間の代償でO（ln N）である。

Answer 2

行列がどのように見えるかについての前提がない場合は、ブルートフォース法を使用して、[X、Y]の近くのすべての値を調べる必要があります。ただ、中心にある[X、Y]位置に3x3の広場を設定し、ゼロ以外の値が見つからない場合は

境界平方上のすべての値をテストし、ちょうど正方形の5x5のを続行

1. 7x7など、あなたが何かを見つけるまで。大きな行列の境界を処理する必要があります。

これは単なるサイクル、インデックス、適切なifsのための仕事です:-)情報がないため、ガイドラインがないため、アルゴリズムが高速になりません。

Answer 3

これは、0以外の値を含むことが予想される行数に依存します。 1000x1000のグリッドに<個の100個の位置があると予想される場合は、値を生成している間に、どの行の情報が0以外であるかの情報を格納する必要があります。

このようなオプションを利用気にいらないthatsの場合：あなたはすでに、検索領域をフィルタリングすることでこれを最適化することができますが、私はそれが唯一のxから高い距離で違いを生むだろうと思う、Y

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 
}