[算法题]求数组交集

Question

有两个长度分别为m,n的升序整型数组，其中n>m*m,求这两个数组的交集，要求复杂度尽可能低。如数组a:-1,4,5
数组b:-15，1，3，4，5，7，8，9，10，15
结果应该是：4，5
带不带猜的，假定长数组中目标数平均分布且恰好为最后一个，那就只需要短数组与长数组划分之后的最后一个数字比较。以上纯属YY。

Answer 1

因为题目说 n>m*m，也就意味着 m 数组比较少，而 n 数组巨大；这个应该是关注点。所以考虑以 m数组 为循环主驱动，大致如下：
1、逐个遍历 m数组 ，元素设为 x
2、    用二分法定位 x 在 n数组 中的位置（可能找不到），找到则输出；
3、    因为是升序，所以下一次搜索下限定在 n数组 中不大于 x 位置；
4、循环指导 m数组 遍历完毕。

Answer 2

        int[] a = {-1,4,5};
        int[] b = {-15,1,3,4,5,7,8,9,10,15};
        int init = 0;
        List<Integer> rtnList = new ArrayList<Integer>();
        for(int i = 0;i<a.length;i++) {
            for(int j = init;j<b.length;j++){
                if (a[i] == b[j]) {
                    init=j+1;
                    rtnList.add(a[i]);
                    break;
                }
            }
        }

Answer 3

又优化了一下：
int[] a = {-1,4,5};
        int[] b = {-15,1,3,4,5,7,8,9,10,15};
        int init = 0;
        List<Integer> rtnList = new ArrayList<Integer>();
        for(int i = 0;i<a.length;i++) {
            for(int j = init;j<b.length;j++){
                System.out.println("[i:"+i+"][a[i]:"+a[i]+"][j:"+j+"][b[j]:"+b[j]+"]");
                if (a[i] == b[j]) {
                    init=j+1;
                    rtnList.add(a[i]);
                    System.out.println("break");
                    break;
                } else if (a[i] < b[j]) {
                    init=j+1;
                    System.out.println("break");
                    break;
                }
            }
        }

Answer 4

public static void find2(int[] a, int[] b) {
int ia = 0, ib = 0;
while (ia < a.length) {
while (ib < b.length) {
if(b[ib] > a[ia]) break;
else if(b[ib] == a[ia]){
++ib;
System.out.println(a[ia]);
break;
}
++ib;
}
++ia;
}
}

Answer 5

我这里有个复杂度比较高的，请高手改善。
public class Intersaction { static int[] a = new int[] { -1, 4, 5, 15, 4 };//需要求交的数组
static int[] b = new int[] { -15, 1, 3, 4, 5, 7, 8, 9, 10, 15 };//需要求交的数组 public static void main(String[] args) {
List<Integer> intersactionList = new ArrayList<Integer>();//存放交集
for (int c : a) {
for (int d : b) {
if (c == d) {
boolean exists = false;//判断元素是否已经在intersactionList中
for (Integer integer2 : intersactionList) {
if (c == integer2) {
exists = true;
}
}
if (exists == false) {
intersactionList.add(c);//假如不在就添加
}
}
}
}
for (Integer integer : intersactionList) {
System.out.println(integer);//输出交集
}
}}

Answer 6

//方法有点简单，不知道是不是你想用的
public class LianXi {
public static void main(String[] args) {
int[] a={-1,4,5};
int[] b={-15 ,1 ,3 ,4 ,5 ,7 ,8 ,9 ,10 ,15};
int k=0;
for (int i=0;i<a.length;i++){
for(int j=k;j<b.length;j++){
if(a[i]==b[j]){
System.out.print(a[i]+" ");
k=j;
//System.out.println("K="+k);
}
}
}
System.out.println();
}
}

Answer 7

这个算法的最大复杂度应该是：O(m+n)

Answer 8

import java.util.ArrayList;
import java.util.List;public class Test7 { public static void main(String[] args) {

int[] a = {-1,4,5};
int[] b = {-15 ,1 ,3 ,4 ,5 ,7 ,8 ,9 ,10 ,15};
List<Integer> list = new ArrayList<Integer>();
for (int i:a){
list.add(i);
}
for (int j:b){
if (list.indexOf(j)!=-1){
System.out.println(j);
}
}
}
}

Answer 9

1、直接将b数组遍历存放到hashMap中，然后遍历a数组，判断是不是在Map中。O(m+n)
2、参考快排交换数据思想。O(m+n) + 比较次数 m+n,eg:
public static void main(String[] args) {
int[] a = {-1,4,5};
int[] b = {-15,1,3,4,5,7,8,9,10,15}; int i = 0,j = 0;
int alen = a.length;
int blen = b.length;

while(i<alen && j<blen){
if(a[i]<b[j]){
i++;
}else if(a[i] == b[j]){
System.out.print(a[i] + "\t");
i++;
j++;
}else{
j++;
}
}
}

Answer 10

怎么感觉是 O(m * log(n)) ... log底数为2

Answer 11

楼主说是有序数组了
int[] a = { -1, 4, 5 };
int[] b = { -15, 1, 3, 4, 5, 7, 8, 9, 10, 15 };
int[] c = new int[a.length];
int i = 0, j = 0, k = 0;
for (; i < a.length && j < b.length;) {
if (a[i] < b[j])
i++;
else if (a[i] > b[j])
j++;
else {
c[k] = a[i];
i++;
j++;
k++;
}
}
for (int l = 0; l < k; l++)
System.out.println(c[l]);

Answer 12

二分法
貌似复杂度n * log2m

Answer 13

不知道你这个 二分查找是如何弄的，能给个demo么？
我的线性查找，但是必须保证数组有序。
    int a[3]={-1,4,5};
    int b[10]={-15,1,3,4,5,7,8,9,10,15};
    int k = 0 , j = 0;
    for(; k < 3 ;) {
        if(a[k] > b[j]) {
            j++;
        }else if(a[k] == b[j]) {
            printf("b[%d]=%d\n",j,b[j]);
            j++;//不知道有没有重复的元素，如果有的话用j++,如果没有重复元素，用j++;k++;
        }else {
            k++;
            if(k > 2) {//当b比a大的时候表示b中已经没有与a匹配的元素了
                break;
            }
        }
    }
    printf("k %d\n" ,k);//循环执行次数m + n - i,i表示第一个比a［m-1］大的元素的位置

Answer 14

顺序便利 ，最坏应该是m+n不是m＊n吧。。