将坐标集转换为排序的二维数组

Question

假设我有一组 n 个坐标 (x, y) 例如 (123, 41), (123, 50), (555, 10), (600, 10)

我想将其转换为二维数组，其中：

列数等于唯一的x坐标数
行数等于唯一的y坐标数
没有两组坐标会完全相同，并且对 x 和 y 的值可以是什么没有限制。
坐标位于相对于所有其他坐标的 x 和 y 的索引处。例如。 (555,10) 具有第二大 x 坐标 (x=1) 和最小 y 坐标之一 (y=0)，因此它的位置将为 [1][0]

x=0 x=1 x=2

y=0 null (555, 10) (600, 10)

y=1 (123, 41) null null

y=2 (123, 50) null null

（有 3 个唯一的 x 坐标（123、555、666）和 3 个唯一的 y 坐标（41、50、10）所以数组是 3x3）

如上所述，我可以使用什么算法从一组坐标生成二维数组？我试图创建自己的但是当 n 非常大时它非常慢 O(n^2).

Answer 1

这是一个简单的解决方案：

获取所有不同的 x 和 y 坐标并对它们进行排序。
对于每个点，获取它在各自排序数组中的 x 和 y 坐标的位置。将点放在结果数组的这个位置。

类似这样的东西（在 Python 中）：

# cook your dish here
points = [(123, 41), (123, 50), (555, 10), (600, 10)]
x_coords = sorted(list(set(i[0] for i in points))) # all distinct x coordinates
y_coords = sorted(list(set(i[1] for i in points))) # all distinct y coordinates
result = [[0 for i in range(len(x_coords))] for j in range(len(y_coords))]

for i in points:
    x_final = x_coords.index(i[0])
    y_final = y_coords.index(i[1])
    result[y_final][x_final] = i
    
for i in result:
    print(i)

这给出：

[0, (555, 10), (600, 10)]
[(123, 41), 0, 0]
[(123, 50), 0, 0]

您可以根据自己的方便用 None 或 null 替换零。
此方法具有 O(NlogN) 时间复杂度。

Edit：index() 方法可能不是最有效的方法，具体取决于所使用的 language/data 结构。您可以使用二进制搜索来实现相同的功能。

将坐标集转换为排序的二维数组

Convert set of Coordinates into a sorted 2D Array

sorting

algorithm

coordinates

multidimensional-array

	x=0	x=1	x=2
y=0	null	(555, 10)	(600, 10)
y=1	(123, 41)	null	null
y=2	(123, 50)	null	null