【算法】求多个数组中的交集（Java语⾔实现）
简介：
  最近在⼯作中遇到⼀个问题，需要离线⽐较两张Mongodb表的差异：⼤⼩差异，相同的个数。
  所以，我将导出的bson⽂件转成了json⽂件（2G以上），⼀条记录正好是⼀⾏。
问题：
  因此我将以上问题转换成了⽐较两个（本例考虑多个）超⼤数组的交集！所以要求时间复杂度、空间复杂度应该尽可能的低！
降低内存：
  由于要将⽂件的每⼀⾏都读到内存⾥，如果⾏的长度⽐较⼤的话，内存肯定是不够的！
  所以我想到的办法是讲每⼀⾏压缩成md5编码。 String line = md5(line)。然后再将新的line读⼊内存。
  如此，通常1000万⾏记录读到内存⾥⼤概是800MB（这⾥有点忘了，反正⼤概是800MB~1GB）。
（我使⽤的idea编辑器，跟eclipse可能在某些地⽅有点差别。另外，本例⼀字符数组为例，并且假设数组元素不重复）
MapReduce:
/**
* 这⾥以字符串数组为例
* 采⽤mapreduce原理，⽣成⼀组以数组元素为key，相同元素的个数为value的中间键值对
* 这⾥将mapreduce分开来写⽅便阅读，也可以写成⼀个函数
* @param arrays
*/
public static HashMap<String, Integer> mapReduce(final String[]... arrays) {
HashMap<String, Integer> hashMap = new HashMap<>();
// 不要看到两个for就以为时间复杂度为n^2，这⾥只是有多个数组参数⽽已
for (String[] array : arrays) {
for (String elem : array) {
if (ainsKey(elem)) {
hashMap.put(elem, (elem) + 1);
}
else {
hashMap.put(elem, 1);
}
}
}
return reduce(hashMap, arrays.length);
}
Reduce:
/**
* 统计出相同元素个数正好是数组(参数)个数的元素（也就是每个数组中都有的元素）
* 移除value不等于数组参数个数的键值对，并组成新的map
* @param hashMap
* @param arrayCount
* @return
*/
public static HashMap<String, Integer> reduce(HashMap<String, Integer> hashMap, final Integer arrayCount) {
Iterator<String> iter = hashMap.keySet().iterator();
String key;
while(iter.hasNext()) {
key = ();
if (!(key).equals(arrayCount)) {
      　// 不能使⽤ ve(key); 会出现异常, 见wwwblogs/yrqiang/p/5344531.html
}
}
return hashMap;
}
eg:
/**
* 本例假设同⼀数组中的元素不重复
* @param args
*/
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>();    String[] arr1 = {"aa", "bb", "cc", "dd"};
String[] arr2 = {"11", "bb", "cc", "dd", "ee"};java数组字符串转数组
String[] arr3 = {"22", "bb", "cc", "dd", "ee", "ff"};
hashMap = mapReduce(arr1, arr2, arr3);
System.out.println(hashMap);
System.out.println(hashMap.size());
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。