输出两个数组的相同元素（用最优算法）

Question

给定两个数组：
int m[];
int n[];请直接贴代码，谢谢。

Answer 1

我写个最简单的吧，是不是最优的就不知道了public class Test
{
public static void main(String[] args)
{
int[] a = {1, 2, 3, 4, 5};
int[] b = {3, 4, 5, 6, 7};

for (int i = 0; i < a.length; i++)
{
for (int j = 0; j < b.length; j++)
{
if (a[i] == b[j])
{
System.out.println(a[i]);
break;
}
}
}
}
}

Answer 2

不是，你这个循环次数为m*n，是最弱的算法。可以是m+n的，用哈希表来做，具体我就不知道了。

Answer 3

public class SleepTest {
public static void main(String[] args) throws InterruptedException {
        Integer[] a = {1, 2, 3, 4, 5};
        Integer[] b = {3, 4, 5, 6, 7};
        List<Integer> c = new ArrayList<Integer>();
HashSet<Integer> hs = new HashSet<Integer>(Arrays.asList(a));
int count = 0;
while(count<b.length){
if(hs.contains(b[count++])){
c.add(b[count-1]);
}
}
System.out.print(c);
}
}
 } 
不知道这个复杂度多少，一直听说过有m+n的，在以前网上找了一下，没有具体讲解的。

Answer 4

我感觉吧，你这个contains只是把循环次数给屏掉了，实际上还是m*n

Answer 5

还记得list吗。还记得list的相关操作吗？import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> list1 = Arrays.asList(1,2,5,7,8,3,12);
List<Integer> list2 = Arrays.asList(1,2,6,7,9,3,12);
List<Integer> list = new ArrayList<Integer>();
list.addAll(list1);
list.retainAll(list2);
System.out.println(list);
}
}
输出结果：
[1, 2, 7, 3, 12]

Answer 6

好吧。我也这种说服力不强。理论上是可以喜欢m+n;
加入上面是Integer数组.public class SleepTest {
public static void main(String[] args) throws InterruptedException {
int[] result = new int[Integer.MAX_VALUE];
        Integer[] a = {1, 2, 3, 4, 5};
        Integer[] b = {3, 4, 5, 6, 7};
for(int i=0;i<a.length;i++){
result[a[i]]=1;
}
for(int i=0;i<b.length;i++){
if(result[b[i]]==1){
System.out.print(b[i]);
}
}
}
}如果我这样是不是就是m+n呢。
而hashcode的机制感觉就是这样的，而且他的hashcode能更加均匀，也就是说，不是我里面的数组有多大的Integer，我这个容器就要多大。这个就是内部机制，也就是说可以用这种方式，也就是能实现m+n。至于hash列表具体是怎么做的我不清楚。