代码之家 › 专栏 › 技术社区 › IUnknown

交叉记录列表

data-structures list algorithm java

0

IUnknown · 技术社区 · 8 年前

我有两张单子-

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

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

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

考虑到第二个列表可能很大-以最有效的方式实现这一点的数据结构/例程是什么

2 回复 | 直到 8 年前

1

2

Henry 8 年前

你可以做一些一次性的预处理 List<String> RecordIdByPriority 变成一个 HashMap<String, Integer> 将列表中的每个项映射到其在列表中的位置。在您的示例{a->0,d->1,e->2}中。然后通过 RecordId 根据哈希映射查找最小元素的列表。在映射中未找到的元素具有+无穷的隐式优先级。

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

2

0

Jai 8 年前

我认为经典的循环应该还是有效的。

public String getHighestPriorityRecord(List<String> recordIdByPriority, List<String> recordId) {
    for (String record : recordIdByPriority) {
        if (recordId.contains(record)) {
            return record;
        }
    }

    // Not found
    return null;
}

最好的: O(1)
平均值: O(n log n) ?
最坏的: O(n^2)

如果你想加快速度,你可以 recordId 变成一个 HashSet (通过创建 散列集 ),所以 contains() 会是 O(1) ,有效地将此算法的最坏情况转换为 O(n) .