Javascript程序用于查找两个数组中的常用元素

Question

最近我有一个面试问题如下:让我们考虑我们有两个不同长度的排序数组.需要在两个数组中找到共同的元素.

var a=[1,2,3,4,5,6,7,8,9,10];
var b = [2,4,5,7,11,15];
for(var i=0;i<a.length;i++){
    for(var j=0;j<b.length;j++){
        if(a[i]==b[j]){
            console.log(a[i],b[j])
        }
    }
}

我上面写的是这样的.采访者说现在假设有2000个元素,b有3000个元素.那么你如何以更有效的方式写作？

请用示例代码解释您的答案.所以我可以更清楚地理解.

Answer 1

您可以通过检查每个数组的索引来使用嵌套方法,并通过递增索引来查找值.如果找到相等的值,则递增两个索引.

时间复杂度:最大 O(N + M),其中Ñ是阵列的长度a和米是阵列的长度b.

var a = [1, 2, 3, 4, 5, 6, 8, 10, 11, 15], // left side
    b = [3, 7, 8, 11, 12, 13, 15, 17],     // right side
    i = 0,                                 // index for a
    j = 0;                                 // index for b

while (i < a.length && j < b.length) {     // prevent running forever
    while (a[i] < b[j]) {                  // check left side
        ++i;                               // increment index
    }
    while (b[j] < a[i]) {                  // check right side
        ++j;                               // increment
    }
    if (a[i] === b[j]) {                   // check equalness
        console.log(a[i], b[j]);           // output or collect
        ++i;                               // increment indices
        ++j;
    }
}

Answer 2

The easiest way!!

var a = [1,2,3,4,5,6,7,8,9,10];
var b = [2,4,5,7,11,15];

for(let i of a){
  if(b.includes(i)){
    console.log(i)
  }
}


--------- OR --------------

var c = a.filter(value => b.includes(value))
console.log(c)

Answer 3

由于数组已排序，因此二进制搜索是关键。

基本上，您正在搜索数组中的项目。

您将项目与数组的中间索引进行比较（长度 / 2）

如果两者相等，你就找到了。

如果 item 低于数组中间索引处的 item，则将 item 与索引长度 / 4 -> ((0 + length / 2) / 2) 处的索引进行比较，如果它次等，则在索引 ((length / 2) + 长度) / 2 (上半部分的中间) 等等。

这样，如果在示例中您必须在 40 000 长度的数组中搜索项目，更糟糕的是，您会发现该项目不在数组中，并且进行了 16 次比较：

我正在一个具有 40 000 个索引的数组中搜索“某物”，我可以找到的最小索引为 0，最大值为 39999。

"something" > arr[20000]. 让我们假设。我知道现在要搜索的最小索引是 20001，最大值是 39999。我现在正在搜索中间的索引，(20000 + 39999) / 2。

现在，"something" < arr[30000]它限制了从索引 20001 到 29999 的搜索。(20000 + 30000) / 2 = 25000。

"something" > arr[25000], 我必须从 25001 搜索到 29999。 (25000 + 30000) / 2 = 27500

"something" < arr[27500], 我必须从 25001 搜索到 27499。 (25000 + 27500) / 2 = 26250

"something" > arr[26250], 我必须从 26251 搜索到 27499。 (26250 + 27500) / 2 = 26875

"something" < arr[26875], 我必须从 26251 搜索到 26874。 (26250 + 26875) / 2 = 26563

等等......当然，你必须四舍五入以避免浮动索引

var iteration = 1;

function bSearch(item, arr)
{
    var minimumIndex = 0;
    var maximumIndex = arr.length - 1;
    var index = Math.round((minimumIndex + maximumIndex) / 2);

    while (true)
    {
        ++iteration;
        if (item == arr[index])
        {
            arr.splice(0, minimumIndex);
            return (true);
        }
        if (minimumIndex == maximumIndex)
        {
            arr.splice(0, minimumIndex);
            return (false);
        }
        if (item < arr[index])
        {
            maximumIndex = index - 1;
            index = Math.ceil((minimumIndex + maximumIndex) / 2);
        }
        else
        {
            minimumIndex = index + 1;
            index = Math.floor((minimumIndex + maximumIndex) / 2);
        }
    }
}

var arrA;
var arrB;

for (var i = 0; i < arrA.length; ++i)
{
    if (bSearch(arrA[i], arrB))
        console.log(arrA[i]);
}
console.log("number of iterations : " + iteration);