BYR Achieve · 镜像论坛

求两个集合的交集

2017/9/27镜像同步2 回复

转自：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

订阅后，新回复会通过你的通知中心匿名送达。