问题： 给你两个排序的数组，求两个数组的交集?比如： A = 1 3 4 5 7， B = 2 3 5 8 9

 

 

代码实现:

public LinkedList
     
       intersection(int[] A, int[] B) {      if (A == null || B == null || A.length == 0 || B.length == 0) return null;      LinkedList
      
        list = new LinkedList
       
        ();      int pointerA = 0;      int pointerB = 0;      while (pointerA < A.length && pointerB < B.length) {          if (A[pointerA] < B[pointerB]) pointerA++;          else if (A[pointerA] > B[pointerB]) pointerB++;          else {              list.add(A[pointerA]);              pointerA++;              pointerB++;          }      }        return list;    }
       
      
     

 

代码分析:

因为数组A B均排过序，所以，我们可以用两个“指针”分别指向两个数组的头部，如果其中一个比另一个小，移动小的那个数组的指针；如果相等，那么那个值是在交集里，保存该值， 这时，同时移动两个数组的指针。一直这样操作下去，直到有一个指针已经超过数组范围。通过上面的算法可以得知，该算法复杂度为O(N + M).