有两个数组a{1,5,8,10,14,15,17,18,20,22,24,25,28}和b{2,4,6,8,10,12}，如何求出他们之间的交集？要求效率越高越好
注：数组都是从小到大排序好的
------解决方案--------------------
其实解决b中的重复也很简单，只要在遍历b的时候，判断一下当前的这个元素是否和前面的元素一样，如果一样，那就continue执行下一次循环。
所以总结起来看，在这个算法中，如果a是第一个放到set中去的话，那么a有没有排序无所谓；但是为了避免麻烦，b最好是排序的。
好了，代码就不写了。已经分析好了。坐等楼下提供别的算法...
------解决方案--------------------
既然是排序好的,
那么可以直接对比a和b的元素
i,j是a,b中元素的当前位置
- Java code
while(i<a.length && j < b.length){if(a[i] < b[j]){ i++;}else if (a[i] == b[j]){ 输出这个元素; i++; j++;}else{ j++;}}
------解决方案--------------------
------解决方案--------------------
偷懒的写法：
- Java code
int[] a = {1,5,8,10,14,15,17,18,20,22,24,25,28};int[] b = {2,4,6,8,10,12};List list = new ArrayList(Arrays.asList(a)); list.retainAll(Arrays.asList(b)); // list 中的就是交集了.
------解决方案--------------------
代码如下，如果你想降低时间复杂度，可以在getDuplicated方法里多加判断，因为是排过序的，当第二个数组的元素大小超过了第一个数组的最后一个值的时候，就没有必要继续了；还有当前元素如果小于第一个数组的第一个元素是，也没必要继续，直接跳到下一次循环。等等...
- Java code
import java.util.*;public class STest { private static int count, index; public static void getDuplicated(int[] a, int[] b){ Set<Integer> set = new LinkedHashSet<Integer>(); for(int i=0; i<a.length; i++) set.add(a[i]); for(int j=0; j<b.length; j++){ int setSize = set.size(); if(j>0){ if(b[j] == b[j-1]) continue; } set.add(b[j]); if(set.size() == setSize){ b[index] = b[j]; count ++; index ++; } } } public static void main(String[] args) { int[] first = {1,5,8,8,10,100,14,15,70,70,17,18,18,20,22,24,25,28}; int[] second = {2,4,4,4,4,6,8,8,8,8,10,12}; getDuplicated(first, second); for(int i=0; i<count; i++) System.out.print(second[i] +" "); }}
------解决方案--------------------
高效率的上面都说了，我写个低效率的，优点在于没用API中现成的方法，笔试时经常碰到这种变态要求。。。
- Java code
public class TestUnion { public static void main(String args[]){ int a[] = {1,5,8,10,14,15,17,18,20,22,24,25,28}; int b[] = {2,4,6,8,10,12}; for(int i = 0; i < b.length; i++){ for(int j = 0; j < a.length; j++){ if(b[i] == a[j]){ System.out.print(" " + b[i]); break; } else continue; } } }}
------解决方案--------------------
知道散列集HashSet 吗，它在数据组织上类似于数学上的数组，可以进行“交”、“并”、“差”等运算。
例如：
Integer one=new Integer(1),
two=new Integer(2),
three=new Integer(3),
four=new Integer(4),
five=new Integer(5),
six=new Integer(6);
HashSet A=new HashSet(),
B=new HashSet(),
tempSet=new HashSet();
A.add(one);
A.add(two);
A.add(three);