有一个数组M有一些数据,另一个数组N也有一些数据,M中的一些数据N中也有,请有最少循环找出相同的数据
我有了一个方法.
package com.xlh.dao;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
public class SecondFind {
static int[] M = new int[] { 2, 4, 5, 8, 65, 81 };
static int[] N = new int[] { 8, 5, 45, 57, 89, 6, 4, 65, 1, 5, 2 };
static HashMap m = new HashMap();
static int count = 0;
public static void main(String[] args) {
// 输出M和N的长度
System.out.println("M的长度为=" + M.length);
System.out.println("N的长度为=" + N.length);
// find(M,N) ;
// 试试哈希表
hash();
System.out.println("循环了多少次count=" + count);
}
//哈希算法
public static void hash() {
for (int i = 0; i < M.length; i++) {
m.put(i, M[i]);
count++;
}
for (int i = 0; i < N.length; i++) {
//将N的数放到M哈希表的时候判断一下是否有一样的.
if (m.containsValue(N[i])) {
System.out.println("N["+i+"]="+N[i]) ;
} else {
m.put(count,N[i]) ;
}
count++ ;
}
}
// 先用最笨的方法
public static void find(int[] a, int[] b) {
for (int i = 0; i < M.length; i++) {
for (int j = 0; j < N.length; j++) {
if (M[i] == N[j]) {
System.out.println(M[i]);
// break ;
}
count++;
}
}
}
}
我在楼主的基础上做了一些改进，通过测试结果我们得出结论。
list()<hash() , bestlist()<besthash()
说明使用list执行上述操作的效率比hashMap高。
bestlist()<list()
besthash()<besthash()
说明使用长度较大方作为基数与较小方循环判断更有效。
我觉得光考虑次数是不够的，执行时间更为重要，题目要求最小次数的目的最终还是为了追求性能。
以上代码可以直接copy运行。
[code="java"]
package com;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
public class JudgeArrayContain {
static int[] M = new int[100];
static int[] N = new int[100000];
static HashMap m = new HashMap();
static int count = 0;
static List<Integer> result = new ArrayList<Integer>();
static long startDate;
static long endDate;
public static void main(String[] args) {
// 初始化数据
init();
// 输出M和N的长度
System.out.println("M的长度为=" + M.length);
System.out.println("N的长度为=" + N.length);
find(M, N);
// 试试哈希表
hash();
list();
besthash();
bestlist();
}
// 初始化数据
public static void init() {
for (int i = 0; i < 100; i++) {
M[i] = new Random().nextInt(100);
}
for (int i = 0; i < 100000; i++) {
N[i] = new Random().nextInt(100);
}
}
// 哈希算法
public static void hash() {
count = 0;
startDate = System.currentTimeMillis();
for (int i = 0; i < M.length; i++) {
m.put(i, M[i]);
count++;
}
for (int i = 0; i < N.length; i++) {
// 将N的数放到M哈希表的时候判断一下是否有一样的.
if (m.containsValue(N[i])) {
// System.out.println("N[" + i + "]=" + N[i]);
} else {
}
count++;
}
endDate = System.currentTimeMillis();
System.out.println("hash()循环了多少次count=" + count);
System.out.println("hash()执行时间：" + (endDate - startDate));
}
// best哈希算法
public static void besthash() {
count = 0;
if (M.length > N.length) {
startDate = System.currentTimeMillis();
for (int i = 0; i < M.length; i++) {
m.put(i, M[i]);
count++;
}
for (int i = 0; i < N.length; i++) {
// 将N的数放到M哈希表的时候判断一下是否有一样的.
if (m.containsValue(N[i])) {
// System.out.println("N[" + i + "]=" + N[i]);
} else {
}
count++;
}
endDate = System.currentTimeMillis();
System.out.println("besthash()循环了多少次count=" + count);
System.out.println("besthash()执行时间：" + (endDate - startDate));
} else {
startDate = System.currentTimeMillis();
for (int i = 0; i < N.length; i++) {
m.put(i, N[i]);
count++;
}
for (int i = 0; i < M.length; i++) {
// 将N的数放到M哈希表的时候判断一下是否有一样的.
if (m.containsValue(M[i])) {
// System.out.println("M[" + i + "]=" + M[i]);
} else {
}
count++;
}
endDate = System.currentTimeMillis();
System.out.println("besthash()循环了多少次count=" + count);
System.out.println("besthash()执行时间：" + (endDate - startDate));
}
}
// List算法
public static void list() {
count = 0;
startDate = System.currentTimeMillis();
for (int i = 0; i < M.length; i++) {
result.add(M[i]);
count++;
}
for (int i = 0; i < N.length; i++) {
// 将N的数放到M哈希表的时候判断一下是否有一样的.
if (result.contains(N[i])) {
// System.out.println("N[" + i + "]=" + N[i]);
} else {
}
count++;
}
endDate = System.currentTimeMillis();
System.out.println("list()循环了多少次count=" + count);
System.out.println("list()执行时间：" + (endDate - startDate));
}
// best哈希算法
public static void bestlist() {
count = 0;
if (M.length > N.length) {
startDate = System.currentTimeMillis();
for (int i = 0; i < M.length; i++) {
result.add(M[i]);
count++;
}
for (int i = 0; i < N.length; i++) {
// 将N的数放到M哈希表的时候判断一下是否有一样的.
if (result.contains(N[i])) {
// System.out.println("N[" + i + "]=" + N[i]);
} else {
}
count++;
}
endDate = System.currentTimeMillis();
System.out.println("list()循环了多少次count=" + count);
System.out.println("list()执行时间：" + (endDate - startDate));
} else {
startDate = System.currentTimeMillis();
for (int i = 0; i < N.length; i++) {
result.add(N[i]);
count++;
}
for (int i = 0; i < M.length; i++) {
// 将N的数放到M哈希表的时候判断一下是否有一样的.
if (result.contains(M[i])) {
// System.out.println("M[" + i + "]=" + M[i]);
} else {
}
count++;
}
endDate = System.currentTimeMillis();
System.out.println("bestlist()循环了多少次count=" + count);
System.out.println("bestlist()执行时间：" + (endDate - startDate));
}
}
// 先用最笨的方法
public static void find(int[] a, int[] b) {
count = 0;
startDate = System.currentTimeMillis();
for (int i = 0; i < M.length; i++) {
for (int j = 0; j < N.length; j++) {
if (M[i] == N[j]) {
// System.out.println(M[i]);
// break ;
}
count++;
}
}
endDate = System.currentTimeMillis();
System.out.println("find()循环了多少次count=" + count);
System.out.println("执行时间：" + (endDate - startDate));
}
}
[/code]
测试结果1：
[code="java"]
M的长度为=100
N的长度为=100000
find()循环了多少次count=10000000
执行时间：297
hash()循环了多少次count=100100
hash()执行时间：672
list()循环了多少次count=100100
list()执行时间：313
besthash()循环了多少次count=100100
besthash()执行时间：484
bestlist()循环了多少次count=100100
bestlist()执行时间：62
[/code]
测试结果2：
[code="java"]
M的长度为=100
N的长度为=100000
find()循环了多少次count=10000000
执行时间：78
hash()循环了多少次count=100100
hash()执行时间：344
list()循环了多少次count=100100
list()执行时间：125
besthash()循环了多少次count=100100
besthash()执行时间：281
bestlist()循环了多少次count=100100
bestlist()执行时间：31
[/code]
测试结果3：
[code="java"]
M的长度为=100
N的长度为=100000
find()循环了多少次count=10000000
执行时间：94
hash()循环了多少次count=100100
hash()执行时间：453
list()循环了多少次count=100100
list()执行时间：110
besthash()循环了多少次count=100100
besthash()执行时间：281
bestlist()循环了多少次count=100100
bestlist()执行时间：31
[/code]