# 快速的判断两个字符串型数组是否有交集

2015/07/02 19:31

■[面试题]如何快速的判断两个数组是否有交集

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★

0
11 收藏

### 作者的其它热门文章

Arrays是对array的操作，然Collections却不是对Collection的操作。
2015/07/03 05:13

2015/07/03 05:10

#### 引用来自“GenesisKing”的评论

public boolean hasIntersectionByHashSet2(String[] array1, String[] array2) { HashSet set = new HashSet(); HashSet set1 = new HashSet(); for(String str : array2) { // for each set.add(str); } int sa2 = set.size(); for (String str : array1) { // for each set1.add(str); } int sa1 = set1.size(); set.addAll(set1); // for each int sall = set.size(); // System.out.println("@hasIntersectionByHashSet2[" + sa1 + "," + sa2 +"," + sall + "]"); return sall == (sa1 + sa2) ? false : true; }
2015/07/03 05:08

2015/07/03 04:07

2015/07/03 00:19

2015/07/02 21:23

2015/07/02 21:20

2015/07/02 21:14

8 评论
11 收藏
0