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生成的

[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分查找，找到表示交集。

1.两数组先排序
2.在排序的基础上比较,第二个元素可以再第一个元素的基础上进行
不过,怎么实现单层循环实现,暂时没想到. :D

[code="java"]
import java.util.ArrayList;
import java.util.List;

public class ListTest {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    List<String> list1 = new ArrayList<String>(); 
    List<String> list2 = new ArrayList<String>(); 
    list1.add("1"); 
    list1.add("2"); 
    list1.add("3"); 
    list1.add("4"); 
    list1.add("5"); 
    list1.add("6"); 
    list1.add("7"); 
    list1.add("8"); 
    list1.add("9"); 
    list1.add("10"); 

    list2.add("1"); 
    list2.add("3"); 
    list2.add("8"); 


    System.out.println(sameList(list1, list2));

}


public static List<String> sameList(List<String> list1, List<String> list2)
{
    List<String> list = new ArrayList<String>();
    String temp;
    for(int i=0; i < list1.size();i++)
    {
        temp = list1.get(i);
        if(list2.contains(temp)){   
            list.add(temp);   
        }
    }

    return list;

}

}

[/code]

[quote]大部分java库函数实现都用了循环，包括List.contains，Map.containsKey，Map.get等等
排序性能也不高，还是没看到什么好的做法，:( [/quote]
list确实有遍历。
map确没有了。map是采用了hash的方式。你说他们的性能不高？可有什么具体的测试？

[quote]
想问下，map的实现没有循环么？Map.Entry.next这样做迭代不是循环么
[/quote]
Map对key的迭代是循环，相当于遍历所有的key。
但是Map对key的定位却不是循环，而是hash

[quote]
还有，好多地方提到这题的哈希实现的时候都会说是用空间换时间，但是java里具体怎么实现所谓空间换时间的？
[/quote]
这个问题，我想你自己看jdk源代码会更加清楚！