修改已排序的數組的交集

Question

我遇到了這個問題 - 輸入 - 我給了兩個排序數組a1和a2。我需要找到第二個數組中不存在的元素。

我有兩種方法

1）哈希表 - O（M + N）
[使用時第二陣列是小]

2）二進制搜索 - O（M * logn）時間
[當第二個陣列很大時使用]

是否有其他方法具有更好的時間複雜性？

謝謝你

Answer 1

只是並行迭代它們。

這裏是一個JavaScript例如：

var a1 = [1, 2, 3, 4, 5, 6, 7, 9]; 
var a2 = [0, 2, 4, 5, 8]; 

findNotPresent(a1, a2); // [1, 3, 6, 7, 9] 


function findNotPresent(first, second) { 
    var first_len = first.length; 
    var first_index = 0; 

    var second_len = second.length; 
    var second_index = 0; 

    var result = []; 

    while (first_index < first_len && second_index < second_len) { 
     if (first[first_index] < second[second_index]) { 
      result.push(first[first_index]); 
      ++first_index; 
     } 
     else if (first[first_index] > second[second_index]) { 
      ++second_index; 
     } 
     else { 
      ++first_index; 
      ++second_index; 
     } 
    } 

    while (first_index < first_len) { 
     result.push(first[first_index++]); 
    } 

    return result; 
} 

我相信這將需要O（MAX（N，M））。