java - 如何流利地比较 ArrayList 元素？

Question

我想问你如何比较两个列表并获得输出信息，其中第二个列表中的元素是第一个列表的元素。

示例:

第一个列表:a c b

第二个列表:c b a

输出:3 1 2

我试过了:

for(int i = 0 ; i < firstList.size() ; i++)
{
    System.out.println(secondList.indexOf(firstList.get(i)));
}

但是对于大量数据来说它太慢了。我尝试了两个 for 循环，但比这慢。你还有其他建议吗？我想解决这个问题。

Answer 1

对于“大量数据”，无论是一个for 循环调用indexOf 还是两个for 循环，都会很慢。这些 for 循环中的每一个都贡献了 O(n)，甚至 indexOf 这是一个伪装的循环。这些是 O(n²) 算法。

假设所有元素在列表中都是唯一的，您可以遍历其中一个列表，将所需的数字放入 HashMap 中，查找时间为 O(1)。

然后你只需要使用一个for循环，而不是查询HashMap。

Map<String, Integer> map = new HashMap<>();
for(int i = 0; i < secondList.size(); i++)
{
    map.put(secondList.get(i), i + 1);
}
for(int i = 0 ; i < firstList.size() ; i++)
{
    System.out.println(map.get(firstList.get(i)));
}

这是 O(n) 并且对于“大量数据”会表现更好。