Java:在对象数组中搜索 2 个特定对象值

Question

我正在用 Java 做一个项目，其中包括 (x,y) 坐标。我创建了一个 Cell 类，它具有 protected 整数 X 和 Y；初始化后，我执行一个 for 循环，通过将用户给出的 X 和 Y 相乘来设置单元格数组，假设如果 X= 10 且 Y = 10，我将创建一个单元格数组[100]。

但是，如何快速搜索数组，而不执行 for 循环并多次检查每个单独的值？

假设我正在寻找包含 X=5 & y = 3 的对象。我知道我可以通过 for 循环查找具有值 x 和 y 的对象，但我想知道是否有一种方法可以进行二分搜索并找到“更快一点”包含 X=5 的对象[i]且Y=5。

非常感谢。

Answer 1

实现此目的的方法是以某种方式排列数组中的 Cell 对象，以便存在从 X,Y 坐标到数组中 Cell 的索引的简单映射。

例如，假设 X 和 Y 从 1 到 10。假设我们随后排列单元格，以便:

array[0] = Cell(1, 1);
array[1] = Cell(1, 2);
...
array[9] = Cell(1, 10);
array[10] = Cell(2, 1);
array[11] = Cell(2, 2);
...
array[99] = Cell(10, 10);

应该很容易看出，我们可以计算数组中 Cell(i,j) 的索引并获取单元格，如下所示:

public Cell getCell(Cell[] array, int i, int j) {
    int index = (10 * (i - 1)) + (j - 1);
    return array[index];
}

这是支持 N 维数组类型的编程语言通常用来实现它们的方法。

可以对此进行简单修改以处理以下情况:

• 常数 10 是另外一个东西
• 矩阵不是方阵，
• 矩阵的维度超过二维
• 索引从 0 到 N - 1，而不是 1 到 N
• 等等

还有多种其他方法可以在 Java 中表示二维矩阵。最简单的一种是使用 Cell[][] cells，它允许您以 cells[i-1][j-1] 的形式访问单元格。如果矩阵稀疏(即单元丢失)，可以设计更复杂的表示，使用更少的空间，但代价是更复杂的代码和更慢的访问时间。