返回信息流转自： http://www.k6k4.com/blog/show/aaajyefii1506524723567
如：集合A={1,2,3,4}, B={5,3,4}， 结果为：result={3,4}
方法一：排序法
思路：先对两个集合进行排序O(nlogn)，然后通过一遍查询比较O(n), 即可找出两个集合的交集
public static void main(String[] args) {
List<Integer> listA = new ArrayList<Integer>();
listA.add(1);
listA.add(2);
listA.add(3);
listA.add(4);
List<Integer> listB = new ArrayList<Integer>();
listB.add(5);
listB.add(3);
listB.add(4);
//排序O(nlogn)
Collections.sort(listA);
Collections.sort(listB);
//一次遍历O(n)
for (int i = 0, j = 0; i < listA.size() && j < listB.size(); ) {
if (listA.get(i) < listB.get(j)) {
i++;
} else if (listA.get(i) > listB.get(j)) {
j++;
} else {
System.out.print(listA.get(i) + " ");
i++;
j++;
}
}
}
方法二：Hash法
思路：将较小的集合放入hash表里O(n)，然后逐个遍历大表中的每个元素是否在hash表里O(n)，需要消耗O(n)的空间
public static void main(String[] args) {
List<Integer> listA = new ArrayList<Integer>();
listA.add(1);
listA.add(2);
listA.add(3);
listA.add(4);
List<Integer> listB = new ArrayList<Integer>();
listB.add(5);
listB.add(3);
listB.add(4);
//将集合B加入Hash表里，耗时O(n), 空间消耗O(size(listB))
Set<Integer> setB = new HashSet<Integer>();
for (int i = 0; i < listB.size(); i++) {
setB.add(listB.get(i));
}
//一次遍历O(n)
for (int i = 0; i < listA.size(); i++) {
if (setB.contains(listA.get(i))) {
System.out.print(listA.get(i) + " ");
}
}
}
方法三：集合压缩法
http://blog.csdn.net/jie1991liu/article/details/13168255
方法四：位图法
http://blog.csdn.net/moli152_/article/details/48163351
转自： http://www.k6k4.com/blog/show/aaajyefii1506524723567
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #94082同步于 2017/9/27
ACM_ICPC机器人发帖
求两个集合的交集
z1j2q21
2017/9/27镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。