javascript - 使用 javascript 使用算法解决问题

Question

我正在研究下面的例子

Given: 2 sorted arrays of integers(e.g. A = [1,2,3,4,5], B = [6, 7, 8, 9, 10]) and answer(e.g 13)
Find: What I have to do is to find pair of indices(1 in each array) of those two elements in both arrays so when I add them then it should be equal to the given answer.

我使用了以下两种解决方案。但是他们两个的问题是我正在循环遍历两个数组。首先我循环遍历第一个数组，然后在这个数组中循环通过第二个数组。并在这两个索引上添加元素以查看其添加是否等于答案。它工作正常并输出正确答案。问题是表现。如果我们在两个数组中都有 10,000 个整数，那么这些循环将占用大量资源，例如时间、CPU 和内存来执行并获得答案。

如何更有效地解决上述特定问题？

function find (A1, A2, ans) {
  var a = [];
  for (var i = 0, len1 = A1.length; i < len1; i++) {
    for (var j = 0, len2 = A2.length; j < len2; j++) {
      if (ans === A1[i] + A2[j]) {
        a.push(i + ', ' + j);
      }
    }
  }
  return a;
}

第二个

function search (A, B, ans) {
  var arr = [];
  A.map(function (v, i) {
    B.filter(function (val, ind) {
      if (ans === v + val) arr.push(i + ', ' +ind);
    });
  });
  return arr;
}

Answer 1

解决方案1
您可以使用较少的元素遍历数组的所有元素，直到 answer 和在第二个数组中的二进制搜索 (answer - array[index])，此算法的复杂度为 O(N log M )。

Live code in C++

解决方案2
或者您可以在线性时间内合并两个数组并应用以下算法在线性时间内找到对。合并时，保留大小为 N+M 的反向映射数组 mapA 和 mapB，其中 mapA[i] 指向数组 A 中的索引，从合并数组的第 i^th 个数组来否则为-1。对 mapB 也做类似的事情。

/* Merge the arrays */
mapA, mapB, MA all are arrays of size M+N, initialized with all -1
i = 0, j = 0
while(i < M && j < N)
    if(A[i] < B[j])
        MA[i+j] = A[i];
        mapA[i+j] = i++;
    else
        MA[i+j] = B[j];
        mapB[i+j] = j++;
while(i < M)
    MA[i+j] = A[i];
    mapA[i+j] = i++;
while(j < N)
    MA[i+j] = B[j];
    mapB[i+j] = j++;

/* Search the pair */
i = 0
j = N + M - 1
while(i < j){
   if(mapA[i] == -1) i++;
   else if(mapB[j] == -1) j--;
   else if (MA[i] + MA[j] == answer) return pair(mapA[i], mapB[j]);
   else if (MA[i] + MA[j] <  answer) i++;
   else if (MA[i] + MA[j] >  answer) j--;
}
return null_pair;  // no answer found

Live code example in C++

解决方案3
有一个更好的算法(受 3 和算法的启发)在线性时间内工作，即常量空间中的 O(N + M)。

i = 0
j = M - 1
while(i < N && j >= 0){
   if      (A[i] + B[j] == answer) return pair(i, j);
   else if (A[i] + B[j] <  answer) i++;
   else if (A[i] + B[j] >  answer) j--;
}
return null_pair;  // no answer found

证明
让我们假设 A[x] + B[y] = answer。然后 x 将首先到达 i 或 j 将首先到达 y 或者我们将找到一些其他对A[i] + B[j] = 答案。不失一般性，我们假设 x 首先变成 i。现在对于所有 j > y，A[i] + B[j] > answer 所以 j 最终会得出答案。如果没有答案，我们将退出循环。