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

Question

我正在用 Java 做一个项目，其中包括 (x,y) 坐标。 我创建了一个 Cell 类，它保护整数 X &是； 初始化后，我执行一个 for 循环，通过将 X 和 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。假设我们然后排列 Cells，以便：

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) 在数组中的索引并获取cell 如下：

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] 的形式访问单元格。如果矩阵稀疏（即单元丢失），可以设计更复杂的表示，使用更少的空间，但代价是更复杂的代码和更慢的访问时间。

Answer 2

听起来（无论如何，如果您想使用二分搜索）您正在使用 x = 0, y = 0; 将元素 0 设置为单元格；元素 1 到 x = 0, y = 1 等。如果是这样，您应该能够轻松计算给定单元格的确切索引：

// contains the Cell with x = desiredX, y = desiredY
yourArray[desiredX * X + desiredY];

但是，如果这就是您正在做的事情，那么它' d 制作一个二维数组可能更简单：

yourArray = new Cell[X][Y];
...
yourArray[desiredX][desiredY];

Answer 3

上面的两个答案显示了快速获取数组索引的简单方法。我想提出一个替代方案——使用带有键、值对的哈希图。该值可以是对象。访问哈希图元素在恒定时间内运行..