一个疑问：从两个数组查找相同的元素（使用最少的循环次数）解决方法

一个疑问：从两个数组查找相同的元素（使用最少的循环次数）
两个数组分别是：M,N。他们分别含有M个、N个元素(元素可能相同)，请问如果使用最小的循环数查找到两个数组含有的相同的元素？

假设M[]{1,2,3,4,5,6,……}，M[]{2,3,4,5,6,……}。

PS：使用hash表查找，是获得最小循环数的方法吗？如果是，请给出示例代码，谢谢。



[解决办法]
就用两个循环,找到了就break内循环不就好了
[解决办法]
应该是依次循环，遇到相同的就去除来减少循环次数把
[解决办法]
最少的循环数~~
留个记号学习一下最优循环如何写~
[解决办法]

Java code

public static void main(String[] args){        int[] M={1,2,3,4,5,6,7,8,9,1,2,3};        int[] N={5,2,5,6,7,8,9};        Set<Integer> setM=new HashSet<Integer>();        for(int m:M)            setM.add(m);//将数组M添加到setM中为了为了避免M中的重复元素        Set<Integer> setN=new HashSet<Integer>();        for(int n:N)            setN.add(n);//将数组N添加到setN中为了为了避免M中的重复元素        HashBag bag=new HashBag();//HashBag是一个org.apache.commons.collections.bag包中的类，可以很简单的求出两个集合中的交集        bag.addAll(setM);        bag.addAll(setN);        System.out.println(bag); }
[解决办法]
汗！刺激我呢！
   那我想想看
[解决办法]
下面这个方法 要求两个数组是已排序的

Java code
package com.haojia.algorithm;/** * 求两个已排序的数组的交集 *  * @author July *  */public class Intersect {    public static void go(int[] a, int[] b) {        int i = 0;        int j = 0;        while (i < a.length && j < b.length) {            if (a[i] < b[j]) {                i++;            } else if (a[i] > b[j]) {                j++;            } else {                System.out.print(a[i] + " ");                i++;                j++;            }        }    }    public static void main(String[] args) {        int[] a = { 1, 5, 8, 10, 14, 15, 17, 18, 20, 22, 24, 25, 28 };        int[] b = { 2, 4, 6, 8, 10, 12 };        go(a, b);    }}
[解决办法]
Java code
import java.util.Arrays;import java.util.HashSet;import java.util.Random;import java.util.Set;public class SelectBag {    public static int find(int key,int[] N){        int lb=0;        int ub=N.length-1;        int in;        while(true){            in=(lb+ub)/2;            if(N[in]==key)                return in;            else if(lb>ub)                return -1;            else{                if(N[in]<key)                    lb=in+1;                else                    ub=in-1;            }        }    }    public static void main(String[] args){        int[] M=RandomIntArray(30);        int[] N=RandomIntArray(30);        System.out.println(Arrays.toString(M));        System.out.println(Arrays.toString(N));        Set<Integer> list=new HashSet<Integer>();        for(int m:M){            int getInt=find(m,N);            if(getInt!=-1)                list.add(N[getInt]);        }        System.out.println("两个数组中重复的元素有："+list);    }        public static int[] RandomIntArray(int count){        int[] array=new int[count];        Random r=new Random();        for(int i=0;i<count;i++){            array[i]=r.nextInt(100);        }        Arrays.sort(array);        return array;    }    }结果：[1, 3, 8, 11, 12, 20, 22, 22, 31, 34, 37, 40, 41, 45, 48, 49, 50, 51, 57, 69, 72, 73, 84, 84, 85, 93, 93, 93, 98, 98][0, 4, 4, 9, 12, 16, 26, 26, 28, 32, 36, 41, 42, 44, 48, 48, 55, 56, 61, 65, 72, 72, 73, 75, 76, 78, 83, 84, 89, 94]两个数组中重复的元素有：[84, 48, 41, 72, 12, 73] 
 
[解决办法]
我的思想是采用二分查找，让查找的次数尽量减少
[解决办法]
探讨

我的思想是采用二分查找，让查找的次数尽量减少

[解决办法]
探讨

将两个数组放入一个数组
 遍历新数组元素
 只要出现次数多于1次就报出
 这样行吗

[解决办法]
好~~~~~~顶一个~~~~~
[解决办法]
探讨

补充说明一下：这两个数组是无序的哦！

[解决办法]
package sort;

import java.util.Arrays;

public class ArraySame  
{
public static void main(String arg[])
{
int[] array_1 = new int[]{1,2,4};
int[] array_2 = new int[]{5,7,2,3,6,9,1,3};
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]) >=0 )  
     {
     System.out.println( array_2[i]);  
     }
 }  
}

}
[解决办法]
System.out.println( array_2[i]);  打错了，改成  array_1[i]
[解决办法]
和楼上的实现一样只是去除了重复结果:
public static void main(String[] args) {
int param[]={1,2,4,5,6,7,3,9};
int param2[]={3,4,6,9,4,7,8};
Arrays.sort(param);
Arrays.sort(param2);
int result;
int old=0;
int news=0;
System.out.print("两数组之间的公共元素:");
for (int i = 0; i < param2.length; i++) {
result=Arrays.binarySearch(param,param2[i]);
if(result>=0){
news=param[result];
//去除重复的值
if(news!=old){
System.out.print(news+",");
old=news;
}
}
}
}
[解决办法]
排序之后就没必要在对每个元素进行二分查找了，一趟循环比较就出来了。

比如两个数组的长度是m, n(m>n), 那么排序之后最多循环m+n次，最少2n次就够了

[解决办法]
[Quote=引用:] 
 有没有不使用任何JAVA 提供好了的API， 自己实现的原生算法 ？ 
 [/Quote] 
  
 自己会排序不？ 自己会写二分查找法不。那自己去写吧。
[解决办法]
说来说去还是我在10楼写的那种方法
[解决办法]
二分法只适合于全是数字类型的数组，要是遇到字母型的就不能用了，其实没有什么很好的办法，查询的时间复杂度是o（m*n），基本上每比较一次都是一个数组遍历过程。比较相同就break ，能平均节省一半时间。
[解决办法]
两个数组无序就让他先有序 然后再归并
[解决办法]
探讨

二分法只适合于全是数字类型的数组，要是遇到字母型的就不能用了，其实没有什么很好的办法，查询的时间复杂度是o（m*n），基本上每比较一次都是一个数组遍历过程。比较相同就break ，能平均节省一半时间。

[解决办法]
这么多讲排序的 我想问下排序时候的循环算不算数
[解决办法]
算了吧 还是两层循环实际点

Java code
    public static void main(String[] args) {        int[] a = { 1, 2, 3, 4 };        int[] b = { 2, 5, 4 };        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]);                }            }        }    } 
 
[解决办法]
13楼正解。我来晚了
[解决办法]
作業？ 飛過
[解决办法]
mark
[解决办法]
用map来做，循环次数是最少的，代码如下：
Java code
package com.test.sort.limit;import java.util.Map;import java.util.HashMap;public class SortData {    /**     * @param args     */    public static void main(String[] args) {        // TODO Auto-generated method stub        int[] arrayA = new int[10];        int[] arrayB = new int[10];                for (int a = 0; a < 10; a++){            arrayA[a] = a+1;            arrayB[a] = a+2;        }                Map<String, Object> map = new HashMap<String, Object>();                for (int i = 0; i < 10 ; i ++){            map.put(String.valueOf(arrayA[i]), 0);  //将数组一中的值放入map中        }        for (int j = 0; j < 10; j++){            boolean isIn = map.containsKey(String.valueOf(arrayB[j]));  //是否第二个数组的值存在于第一个数组            if (isIn){                               //存在的话则相应值的次数加1                int temp = (Integer)map.get(String.valueOf(arrayB[j]));                map.put(String.valueOf(arrayB[j]), temp+1);                            }            else                              //不存在则新加个值                map.put(String.valueOf(arrayB[j]), 0);            }                System.out.println(map.toString());    }}
[解决办法]
探讨

引用:
算了吧 还是两层循环实际点

Java codepublicstaticvoid main(String[] args) {int[] a= {1,2,3,4 };int[] b= {2,5,4 };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]);
                }
            }
        }
    }


无语了 这个是个人都会 对吗？ 呵呵。

[解决办法]
还有 37楼的  我在10楼写的那种方法你不能写 我已经写过了
[解决办法]
我开始写的那个就要求先排序

但是 难道排序不需要遍历吗

还不如直接两层循环