[算法题]求数组交加

[算法题]求数组交集

有两个长度分别为m,n的升序整型数组，其中n>m*m,求这两个数组的交集，要求复杂度尽可能低。

如数组a:-1,4,5
数组b:-15，1，3，4，5，7，8，9，10，15
结果应该是：4，5
带不带猜的，假定长数组中目标数平均分布且恰好为最后一个，那就只需要短数组与长数组划分之后的最后一个数字比较。以上纯属YY。
[解决办法]
顺序遍历，O(m)。
平方的条件没用上。
[解决办法]
因为题目说 n>m*m，也就意味着 m 数组比较少，而 n 数组巨大；这个应该是关注点。

所以考虑以 m数组 为循环主驱动，大致如下：
1、逐个遍历 m数组 ，元素设为 x
2、    用二分法定位 x 在 n数组 中的位置（可能找不到），找到则输出；
3、    因为是升序，所以下一次搜索下限定在 n数组 中不大于 x 位置；
4、循环指导 m数组 遍历完毕。
[解决办法]

引用:

顺序遍历，O(m)。
平方的条件没用上。

哦，最坏是m*n
[解决办法]

        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;
                }
            }
        }

[解决办法]
又优化了一下：

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;
                }
            }
        }

[解决办法]

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;
}
}

[解决办法]
我这里有个复杂度比较高的，请高手改善。
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);//输出交集
}
}

}
[解决办法]
//方法有点简单，不知道是不是你想用的
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();
}
}
[解决办法]

引用:

因为题目说 n>m*m，也就意味着 m 数组比较少，而 n 数组巨大；这个应该是关注点。

所以考虑以 m数组 为循环主驱动，大致如下：

1、逐个遍历 m数组 ，元素设为 x
2、    用二分法定位 x 在 n数组 中的位置（可能找不到），找到则输出；
3、    因为是升序，所以下一次搜索下限定在 n数组 中不大于 x 位置；
4、循环指导 m数组 遍历完……

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

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);
}
}
}
}

[解决办法]
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++;
}
}
}
[解决办法]

引用:

引用:因为题目说 n>m*m，也就意味着 m 数组比较少，而 n 数组巨大；这个应该是关注点。

所以考虑以 m数组 为循环主驱动，大致如下：
1、逐个遍历 m数组 ，元素设为 x
2、    用二分法定位 x 在 n数组 中的位置（可能找不到），找到则输出；
3、    因为是升序，所以下一次搜索下限定在 n数组 中不大于 x 位……

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

查看更多 下一篇