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

Question

    两个数组分别是：M,N。他们分别含有M个、N个元素(元素可能相同)，请问如果使用最小的循环数查找到两个数组含有的相同的元素？假设M[]{1,2,3,4,5,6,……}，M[]{2,3,4,5,6,……}。PS：使用hash表查找，是获得最小循环数的方法吗？如果是，请给出示例代码，谢谢。

Answer 1

就用两个循环,找到了就break内循环不就好了

Answer 2

for(m){
……
for(n)
……
}是错的。

Answer 3

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);
 } 结果：[1:1,2:2,1:3,1:4,2:5,2:6,2:7,2:8,2:9]
PS：A:B，A代表重复个个数，B代表元素

Answer 4

这个可不行哦，调一调别人的API就完了。能否有自己实现的代码啊？！

Answer 5

下面这个方法 要求两个数组是已排序的
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);
}}

Answer 6

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]

Answer 7

1. 那就先排序2. 循环最短的数组。3. 二分查找法找交集。这些 java.util 都有现成的方法。

Answer 8

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]);   
     }
 } 
}

}

Answer 9

System.out.println( array_2[i]);  打错了，改成  array_1[i]

Answer 10

和楼上的实现一样只是去除了重复结果:
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;
}
}
}
}

Answer 11

排序之后就没必要在对每个元素进行二分查找了，一趟循环比较就出来了。比如两个数组的长度是m, n(m>n), 那么排序之后最多循环m+n次，最少2n次就够了

Answer 12

  有没有不使用任何JAVA 提供好了的API， 自己实现的原生算法 ？

Answer 13

自己会排序不？   自己会写二分查找法不。那自己去写吧。
[/Quote]排序也有很多算法的,java API 中的sort算法如下 ：
 /**
     * Sorts the specified sub-array of longs into ascending order.
     */
    private static void sort1(long x[], int off, int len) {
// Insertion sort on smallest arrays
if (len < 7) {
    for (int i=off; i<len+off; i++)
for (int j=i; j>off && x[j-1]>x[j]; j--)
    swap(x, j, j-1);
    return;
}
这个效率不高，明白我的意思么？

Answer 14

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

Answer 15

谁说二分查找法不可以用字符型里面，字符也有对应的 Ascii码的。Arrays类下的二分查找法就可以排序字符型。

Answer 16

算了吧 还是两层循环实际点
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]);
}
}
}
}

Answer 17

用map来做，循环次数是最少的，代码如下：
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());
}}

Answer 18

将2个数组先进行合并然后放到map里去，最后用map的长度减去数组的长度得到的就是2个数组中重复元素的个数

Answer 19

Map map=new HashMap();
Integer[] arrN={1,2,3,4,5,6,7,8,9};
Integer[] arrM={1,3,2,5,9,1};
for(int i=0;i<arrN.length;i++){
map.put(""+arrN[i], arrN[i]);
}
for(int j=0;j<arrM.length;j++){
if(map.get(""+arrM[j])!=null){
System.out.println("相同的元素有"+arrM[j]);
}
}

Answer 20

对数组a建立hash表，然后用数组b中的元素在a中做查找。