所以问题是这样的。我有以下作为示例输入，
|身份证号| 一个 | 乙|
|2 |100|200|
|3 |110|190|
|4 |105|145|
|1 |90 |150|
|5 |102|198|
目标如下。对于每个 ID x，计算其他 ID y 的数量，其中 y 的 A 大于 x 的 A 并且 y 的 B 小于 x 的 B。所以上面例子的输出应该是
|ID|计数|
|3 |0 |
|4 |0 |
|1 |1 |
|5 |2 |
|2 |3 |
其中 ID 3 的计数为 0，因为它具有最大的 A。显然您可以进行 O(n^2) 穷举搜索，但这将是低效的。
我的算法如下。对输入进行两次排序-一次按A，一次按B，得到
|身份证号| 一个 | 乙|
|1 |90 |150|
|2 |100|200|
|5 |102|198|
|4 |105|145|
|3 |110|190|
和
|身份证号| 一个 | 乙|
|2 |100|200|
|5 |102|198|
|3 |110|190|
|1 |90 |150|
|4 |105|145|
然后从第一个排序表中的第一个 ID（ID=1）开始，获取具有较大 A 值的 ID（即 ID 在其下方 - 2、5、4、3），然后在第二个排序表上查找 ID=1并查看它下面的 ID，每次在原始 ID 集中找到一个时，计数器都会增加 - 在这种情况下，第二个表中低于 1 的唯一 ID 是 4，而 4 在 {2,5,4,3}所以输出为1。
所以排序是 O(nlogn)，我相信其余的操作是不变的。有没有更好的方法？