寻找二维数组中的非空网格单元格

我有一个二维整数数组（例如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

寻找二维数组中的非空网格单元格

回答

相关问题