java - 交叉记录列表

Question

我有 2 个列表 -

• List<String> RecordIdByPriority和
• List<String> RecordId .

顾名思义 - 第一个列表包含按插入优先顺序排列的记录。
这个想法是从第二个列表中找到最高优先级记录的存在。

如果优先列表包含<A,D,E> ，第二个包含 <B,E,M> - 预期输出为“E”。

鉴于第二个列表可能很大 - 以最有效的方式实现此目的的数据结构/例程是什么

Answer 1

您可以进行一些一次性预处理，将 List<String> RecordIdByPriority 变为进入HashMap<String, Integer>将列表中的每个项目映射到它在列表中的位置。在您的示例中 { A -> 0, D -> 1, E -> 2 }。然后单次通过 RecordId list根据hash map找到最小元素。在 map 中找不到的元素具有 +infinity 的隐式优先级。

这意味着您可以在 O(n) 中找到元素，其中 n 是记录 ID 列表的长度。