data-structures - Adobe 面试 : What data structure to use for storing thousands of points (x, y) 以更快地执行某些操作

Question

我们必须存储数千个点 (x,y,c) c 这里是该点的颜色。主要与屏幕上的像素有关。我们必须执行操作:
给定 x = i，我们必须改变所有具有 x = i 的点的颜色。
类似地，给定 y = i，我们必须改变所有具有 y = i 的点的颜色。

我提出了一个二维矩阵的解决方案。然后为 x 和 y 坐标分离哈希表。
然后他问我更好的解决方案。
我们可以使用哪些更好的数据结构组合？

Answer 1

您不需要二维数组和单独的哈希表。如果您的数据很密集，代表所有(或大部分)矩形区域，那么 2D 数组本身就足够了。您可以询问哪个坐标最有可能用于查找，然后将数组结构化为外部坐标，以便该坐标中的查找在内存中本地化，否则您无法做得更好。相反，对于稀疏数据，哈希表是您能做的最好的事情。 (我假设您正在将坐标散列到点对象数组中。)是否提供了有关数据性质或最有可能使用方式的更多信息？