一个疑问：从两个数组查找相同的元素（使用最少的循环次数）
两个数组分别是：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]
[解决办法]
我的思想是采用二分查找，让查找的次数尽量减少
[解决办法]
[解决办法]
[解决办法]
好~~~~~~顶一个~~~~~
[解决办法]
[解决办法]
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 ，能平均节省一半时间。
[解决办法]
两个数组无序就让他先有序 然后再归并
[解决办法]
[解决办法]
这么多讲排序的 我想问下排序时候的循环算不算数
[解决办法]
算了吧 还是两层循环实际点
- 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()); }}
[解决办法]
[解决办法]
还有 37楼的 我在10楼写的那种方法你不能写 我已经写过了
[解决办法]
我开始写的那个就要求先排序
但是 难道排序不需要遍历吗
还不如直接两层循环