我有一个二维整数数组(比如 1000 x 1000)，我们称它为矩阵。此矩阵中的每个单元格都有一个 X 坐标和 Y 坐标(在本例中分别为 0 到 999)。最初所有网格单元的值为 0。在程序运行期间，一些矩阵单元被设置为另一个值 <> 0。
现在我需要一个快速函数(算法)，它接受一些 X 和 Y 值并返回矩阵在该坐标处的值。但是，如果指定 X/Y 位置的矩阵为 0，则算法应在矩阵内确定一个尽可能接近原始 X/Y 位置的非零值。
我考虑过在每个循环周期增加偏移量的情况下围绕原始 X/Y 位置循环，但我不确定这是否真的是最快的算法...
有什么想法吗？我更喜欢 Java 代码，但任何伪代码也可以:)
在此先感谢您的帮助! 亲切的问候，马蒂亚斯
最佳答案
如果数组相对稀疏并且测试次数相对于插入次数较多，则朴素方法可能需要很长时间。
另一种方法是构建空间分区树，例如四叉树或 k-d 树。最近邻搜索的复杂度为 O(ln N)，插入时间为 O(ln N)。
关于java - 在二维数组中查找非空网格单元，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7350938/