修改排序的数组的交叉口 [英] Modification of Intersection of sorted array

问题描述

我碰到这个问题 - 输入 - 我给两个排序阵列A1和A2。我需要找到未$的第二个数组P中$ psent的元素。

I came across this problem - input - I am given two sorted arrays a1 and a2. I need to find the elements that are not present in the second array.

我有两种方法

1）哈希表 - O（M + N）
            [使用时，第二排是小]

1) Hashtable - O(m+n)
[use when second array is small]

2）的二分查找 - O（M * LOGN）
[使用时，第二排是巨大的]

2) Binary Search - O(m*logn)
[use when second array is huge]

还有没有其他的方法有较好的时间复杂度？

Are there any other approaches with better time complexities?

感谢您

推荐答案

只是重复它们并行。

下面是一个JavaScript的例子：

Here's a JavaScript example:

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））。

I believe it will take O(max(N, M)).

这篇关于修改排序的数组的交叉口的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！