■[面试题]如何快速的判断两个数组是否有交集
public boolean hasIntersection(String[] array1, String[] array2) {
...
}
array1中，只要有一个在array2中，存在，就返回true，否则返回false
求最快的方法
原帖：
■代码
--------------------------------------------------------------------------------
package javay.test;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.TreeMap;
public class TestIntersection {
public boolean hasIntersectionByHashMap(String[] array1, String[] array2) {
HashMap<String, String> map = new HashMap<String, String>();
for(String str : array2) {
map.put(str, str);
}
for (String str : array1) {
if (map.get(str) != null) {
return true;
}
}
return false;
}
public boolean hasIntersectionByTreeMap(String[] array1, String[] array2) {
TreeMap<String, String> map = new TreeMap<String, String>();
for(String str : array2) {
map.put(str, str);
}
for (String str : array1) {
if (map.get(str) != null) {
return true;
}
}
return false;
}
public boolean hasIntersectionByIndexOf(String[] array1, String[] array2) {
String map = Arrays.toString(array2);
for (String str : array1) {
if (map.indexOf(str) > -1) {
return true;
}
}
return false;
}
public boolean hasIntersectionBySortBS(String[] array1, String[] array2) {
Arrays.sort(array2);
for (String str : array1) {
if (Arrays.binarySearch(array2, str) > -1) {
return true;
}
}
return false;
}
public boolean hasIntersectionByPQueue(String[] array1, String[] array2) {
PriorityQueue<String> queue = new PriorityQueue<String>(array2.length);
for(String str : array2) {
queue.offer(str);
}
for (String str : array1) {
if (queue.contains(str)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
int nMax = 4000000;
String[] b = new String[nMax];
for (int i = 0; i < nMax ; i ++) {
b[i] = String.valueOf(i);
}
String[] t = new String[1];
t[0] = String.valueOf(nMax - 1) + "x";
TestIntersection proc = new TestIntersection();
long a = System.currentTimeMillis();
System.out.println("HashMap:" + proc.hasIntersectionByHashMap(t, b) + "," + (System.currentTimeMillis() - a));
a = System.currentTimeMillis();
System.out.println("TreeMap:" + proc.hasIntersectionByTreeMap(t, b) + "," + (System.currentTimeMillis() - a));
a = System.currentTimeMillis();
System.out.println("IndexOf:" + proc.hasIntersectionByIndexOf(t, b) + "," + (System.currentTimeMillis() - a));
a = System.currentTimeMillis();
System.out.println("PQueue :" + proc.hasIntersectionByPQueue(t, b) + "," + (System.currentTimeMillis() - a));
a = System.currentTimeMillis();
System.out.println("SortBS :" + proc.hasIntersectionBySortBS(t, b) + "," + (System.currentTimeMillis() - a));
for (int i = (nMax - 1); i >= 0 ; i --) {
b[nMax - i - 1] = String.valueOf(i);
}
System.out.println();
a = System.currentTimeMillis();
System.out.println("HashMap:" + proc.hasIntersectionByHashMap(t, b) + "," + (System.currentTimeMillis() - a));
a = System.currentTimeMillis();
System.out.println("TreeMap:" + proc.hasIntersectionByTreeMap(t, b) + "," + (System.currentTimeMillis() - a));
a = System.currentTimeMillis();
System.out.println("IndexOf:" + proc.hasIntersectionByIndexOf(t, b) + "," + (System.currentTimeMillis() - a));
a = System.currentTimeMillis();
System.out.println("PQueue :" + proc.hasIntersectionByPQueue(t, b) + "," + (System.currentTimeMillis() - a));
a = System.currentTimeMillis();
System.out.println("SortBS :" + proc.hasIntersectionBySortBS(t, b) + "," + (System.currentTimeMillis() - a));
}
}
--------------------------------------------------------------------------------
■测试结果
HashMap:false,4744
TreeMap:false,7159
IndexOf:false,875
PQueue :false,499
SortBS :false,469★
HashMap:false,6326
TreeMap:false,4666
IndexOf:false,495
PQueue :false,453
SortBS :false,421★
但也有例外的结果。
HashMap:false,4635
TreeMap:false,7257
IndexOf:false,859
PQueue :false,468★
SortBS :false,484
HashMap:false,6344
TreeMap:false,4712
IndexOf:false,588
PQueue :false,437
SortBS :false,417★