java - 如何在嵌套循环中找到 ArrayList 中某些内容的位置？

Question

有没有办法比较两个 arrayList 以查看它们中的任何一个在任何时候是否具有相同的值？我知道我可以使用两个嵌套循环，但是我试图在 log(n) 时间内执行此操作，因此，我尝试以类似于合并排序中合并两个列表的方式执行此操作，但是我真的不能弄清楚如何具体实现它。任何帮助将不胜感激!谢谢! 编辑:是的，我的意思是 nlog(n)，而不是 log(n)，抱歉

Answer 1

您无法在 O(log(n)) 中完成此操作。

您可以使用 O(n*log(n)) 实现此目的，首先对两个列表进行排序，然后按元素进行比较(排序需要 nlogn 并比较 n)

你可以这样做:

1. 创建变量i, j并初始化为0

2. 循环列表并将 l1.get(i) 与 l2.get(j)

3a。 equal:同时增加i, j(并且可能记住元组)

3b。 l1 的元素小于 l2 的元素:仅增加 i

3c。 l1 的元素大于 l2 的元素:仅增加 j

如果一个索引超出范围，则退出循环

您不需要扫描列表来查找未越界的索引，因为您只对相等的值感兴趣。