【死磕算法系列】两个有序数组的公共部分_求两个数组的公共元素

【死磕算法】 两个有序数组的公共元素

问题提出

给定有序数组A和有序数组B，数组长度分别为M和N，求数组的公共元素。例如：

A = {0, 1, 4, 9, 10}

B = {1, 4, 8, 9, 11}

A和B的公共元素为1，4，9

一、最容易解法

依次从数组A中取数据，挨个到B中去遍历。

如果B中有，说明是公共元素，输出；否则就是没有。

第一次，取0到B中挨个比较，没有；

第二次取1，到B中比较，有，输出。

依次类推。

代码如下：

public static void commonSortedArr1(int[] A, int[] B) {

     for (int i = 0; i < A.length; i++) {
          for (int j = 0; j < B.length; j++) {
             if (A[i] == B[j]) {
                 System.out.print(A[i] + "\t");
                 continue;
              }
            }
      }
      System.out.println();
}
1
2
3
4
5
6
7
8
9
10
11
12

这种解法是最容易想到的，时间复杂度为O(M*N)。

不是最优解。

下面开始做优化。

二、使用二分查找

上面的代码很容易想到一个优化点，从A中取一个数，到B中去查找是否存在，可以使用二分查找，把查找的时间复杂度有O(N)降为O(logN).

public static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
}

public static void commonSortedArr2(int[] A, int[] B) {

        for (int i = 0; i < A.length; i++) {

            if (binarySearch(B, A[i]) >= 0) {
                System.out.print(A[i] + "\t");
            }
        }

        System.out.println();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

这种时间复杂度为O(M*logN).

是否还可以继续优化？

三、使用hash

想到使用hash，把数组A中的元素都放入hashset中。

然后依次判断B中的元素是否存在于hashset中。

public static void commonSortedArr3(int[] A, int[] B) {

    HashSet<Integer> common = new HashSet<>();

    for (int i = 0; i < A.length; i++) {
        common.add(A[i]);
    }

    for (int j = 0; j < B.length; j++) {
        if (common.contains(B[j])) {
            System.out.print(B[j] + "\t");
        }
    }

    System.out.println();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

分析一下时空复杂度：A中的元素加入Hashset，时间复杂度为O(M).

遍历B中的元素做判断，时间复杂度为O(N).

总时间复杂度为O(M+N),额外的空间复杂度为O(M).

比二分查找的方式要好。

那么空间复杂度是否可以降为O(1)？

四、双指针法

使用两个指针i和j分别指向数组A和B，分布从A和B的第一个元素开始移动。

移动规则是：谁小谁往前走，谁大谁不动，相等时同时移动。

指针指向的数值相等时就是公共元素。

A = {0, 1, 4, 9, 10}

B = {1, 4, 8, 9, 11}

i指向A的第一个元素0，j指向B的第一个元素1.

0比1小，i++，此时i指向A的第二个元素1，j没有动。

此时i和j指向的元素数值相同，输出1，i++，j++。

此时i指向4，j指向4.

输出4，i++，j++。i指向9，j指向8。

8小于9，j++，j指向9。

输出9，i++，j++。

10不等于11，数组到头，结束。

A或者B有一个到头，就应该终止循环。

代码如下：

public static void commonSortedArr4(int[] A, int[] B) {

    for (int i = 0, j = 0; i < A.length || j < B.length; ) {
        if (i == A.length || j == B.length) {
            break;
        }

        if (A[i] == B[j]) {
            System.out.print(A[i] + "\t");
            i++;
            j++;
        } else if (A[i] > B[j]) {
            j = j + 1;
        } else {
            i = i + 1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

分析时空复杂度：最坏情况下指针i移动M步，指针j移动N步。

时间复杂度为O(M+N)。

不需要额外的空间。