algorithm - 关于在数组中查找值的问题

Question

我前几天看到过这样的问题

there is given two array find      elements which are common   of these array

解决方案之一是对大数组进行排序，然后使用二进制搜索算法
还有另一种算法-暴力算法

 for (int i=0;i<array1.length;i++){
  for (int j=0;j<array2.length;j++){
 if (array1[i]==array2[j]){
//code here
}
}

它的复杂度是 O(array1.lengtharray2.length); 我感兴趣的是第一种方法的复杂性也是一样的是吗？ 因为我们应该先对数组进行排序，然后再使用搜索方法 二进制搜索算法的复杂度是 log_2(n) 所以这意味着总时间将是 array.lengthlog_2(n) 和关于排序？ 请解释一下哪个更好

Answer 1

一个O(M log N)解决方案

设arr1的长度为O(M)，arr2的长度为O(N)。排序/二进制搜索算法是 O(M log N)。

伪代码如下:

SORT(arr2)   # N log N

FOR EACH element x OF arr1             # M
   IF binarySearch(x, arr2) is FOUND   # log N
       DECLARE DUP x

O(M log N) 大大优于O(MN)。

---

线性时间解决方案

还有第三种方法，即 O(M+N)，使用具有 O(1) 插入和测试的集合。基于散列的集合符合这一期望。

伪代码如下:

INIT arr1set AS emptySet

FOR EACH element x OF arr1    # M
   INSERT x INTO arr1set      # 1

FOR EACH element x OF arr2    # N
   IF arr1set CONTAINS x      # 1
      DECLARE DUP x