[JAVA]两个数组取相同元素，能有单层循环的实现么？

Question

m个元素和n个元素的两个数组（具体没要求，假定没排序，有重复），取其中的相同元素

最近看到个面试题，答案说可以用m+n次循环实现，求算法，最好用java实现。
[b]问题补充：[/b]
大部分java库函数实现都用了循环，包括List.contains，Map.containsKey，Map.get等等
排序性能也不高，还是没看到什么好的做法，:(

m+n的说法是我书上看到的，看来这年头书也不可靠了

[b]问题补充：[/b]

To RyanPoy:
谢谢回复先 :)
排序性能怎样，我暂时没测试。

想问下，map的实现没有循环么？Map.Entry.next这样做迭代不是循环么
还有，好多地方提到这题的哈希实现的时候都会说是用空间换时间，但是java里具体怎么实现所谓空间换时间的？

附HashMap的containsKey和get都用到的：
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {

[b]问题补充：[/b]

自己测试了一下

首先，hash查找确实快，但是对于这题的情况来说，把array put到hash中要花很长时间，普遍情况下，最快的实现还是楼下RyanPoy的先sort在search，再次感谢。

附：
m=n=1000时
Put array to hashtable use 4,508,120ns
Search with Hashtable use 2,861,880ns, found 1
Search with Sort use 6,227,000ns, found 1

m=n=100000时
Put array to hashtable use 108,423,560ns
Search with Hashtable use 30,892,680ns, found 4
Search with Sort use 59,157,680ns, found 4

数组是random生成的

Answer 1

[code="java"]Arrays.sort(array_1);
Arrays.sort(array_2);
int len = array_1.length
for (int i = 0; i < len; i++)
{
if (Arrays.binarySearch(array_2, array_1[i]) != -1)
print array_1[i];
}
[/code]

1) 排序
2）遍历任意数组（如果是短的效果最好，我这里没有做判断）
3）把一个数组的元素在另外一个数组中2分查找，找到表示交集。