algorithm - 映射排序索引

Question

作为更大算法的一部分，我遇到并解决了这个问题，但我的解决方案似乎不够优雅，如果有任何见解，我将不胜感激。

我有一个对列表，可以将其视为笛卡尔平面上的点。我需要生成三个列表:已排序的 x 值、已排序的 y 值和一个列表，该列表将已排序的 x 值中的索引映射到与它最初配对的 y 值相对应的已排序的 y 值中的索引。

一个具体的例子可能有助于解释。给定以下点列表:

((3, 7), (15, 4), (7, 11), (5, 0), (4, 7), (9, 12))

x 值的排序列表为 (3, 4, 5, 7, 9, 15)，y 值的排序列表为 (0, 4, 7, 7, 11, 12)。

假设一个基于零的索引方案，将 x 列表索引映射到其配对的 y 列表索引的索引的列表将是 (2, 3, 0, 4, 5, 1)。

例如，值 7 在 x 列表中显示为索引 3。映射列表中索引3处的值为4，y列表中索引4处的值为11，对应原配对(7, 11)。

生成此映射列表的最简单方法是什么？

Answer 1

这是一个简单的 O(nlog n) 方法:

1. 按 x 值对对进行排序:((3, 7), (4, 7), (5, 0), (7, 11), (9, 12), (15, 4))<
2. 生成一个对列表，其中第一个分量是前一个列表中相同位置的 y 值，第二个分量从 0 开始增加:((7, 0), (7, 1), (0, 2) , (11, 3), (12, 4), (4, 5))
3. 按第一个分量(y 值)对列表进行排序:((0, 2), (4, 5), (7, 0), (7, 1), (11, 3), (12, 4 ))
4. 遍历此列表。对于第 i 个这样的对 (y, k)，设置 yFor[k] = i。 yFor[] 是您的列表(好吧，数组)将已排序的 x 列表中的索引映射到已排序的 y 列表中的索引。
5. 只需从第 1 步生成的列表中删除第二个元素，即可创建排序的 x 列表。
6. 对第 3 步中生成的列表执行相同操作，创建已排序的 y 列表。