两个数组分别是:M,N。他们分别含有M个、N个元素(元素可能相同),请问如果使用最小的循环数查找到两个数组含有的相同的元素?假设M[]{1,2,3,4,5,6,……},M[]{2,3,4,5,6,……}。PS:使用hash表查找,是获得最小循环数的方法吗?如果是,请给出示例代码,谢谢。
解决方案 »
- struts2 中的iterator标签 遍历时怎么取得另一个list中的值
- div显示错位
- 关于jpql的join查询问题
- autoDoc这个插件怎么用啊?(解决给分)
- linux下安装j2sdk-1_4_2_12-linux-i586.bin,出现can't find /usr/bin/sum to do checksum
- eclipse中 Hibernate搭建 报错
- <html:link>中的page 和action属性有什么区别阿?
- struts中新增,编辑页面是如何实现的
- java中如何实现对多数据库的支持?谢谢了!
- 本人课题方向是J2EE构架下搭web,寻J2EE的同路人,我的QQ是8484173,寻友
- 关于c:if标签的一个小问题
- 如何用javascript和jsp实现两级树菜单
……
for(n)
……
}是错的。
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代表元素
这个可不行哦,调一调别人的API就完了。能否有自己实现的代码啊?!
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);
}}
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. 那就先排序2. 循环最短的数组。3. 二分查找法找交集。这些 java.util 都有现成的方法。
{
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]);
}
}
}
}
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;
}
}
}
}
自己会排序不? 自己会写二分查找法不。那自己去写吧。
[/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;
}
这个效率不高,明白我的意思么?
谁说二分查找法不可以用字符型里面,字符也有对应的 Ascii码的。Arrays类下的二分查找法就可以排序字符型。
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]);
}
}
}
}
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());
}}
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]);
}
}