如何流利地比较ArrayList元素

Question

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

示例：

firstList:a c b

secondList: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²(算法。

假设列表中的所有元素都是唯一的，您可以在其中一个列表中运行一次，将所需的数字放在具有O(1(查找时间的HashMap中。

然后您只需要使用一个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(，对于"大量数据"会表现得更好。