使用javascript使用算法解决问题

Solve an issue using algorithm using javascript

本文关键字：算法 解决问题 javascript 使用      更新时间：2023-09-26

我正在研究以下示例

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.

我使用了以下 2 种解决方案。但是它们的问题在于我正在遍历两个数组。首先我遍历第一个数组，在这个数组中循环通过第二个阵列。并在这两个索引上添加元素，以查看其添加是否等于答案。它工作正常并输出正确答案。问题是性能。如果我们在两个数组中都有 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;
}

解决方案1
你可以遍历数组的所有元素，用较少的元素直到答案和二进制搜索第二个数组(answer - array[index])，这个算法的复杂性是O(N log M)。

C++中的实时代码

解决方案2
或者，您可以在线性时间内合并两个数组，并应用以下算法来查找线性时间中的数组对。合并时，保留大小为 N+M 的反向映射数组 mapA 和 mapB，其中 mapA[i] 指向数组 A 中的索引，从第 i个合并数组的数组中出现，否则为 -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

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] = answer.在不失去一般性的情况下，让我们假设x首先成为i。现在对于所有j > y，A[i] + B[j] > answer所以j最终会得到答案。如果没有答案，我们将退出循环。

// get all pairs of number from array a and b, that a[i] + b[j] = sum
// return array of pairs
function getSumPairs(a, b, sum) {
    var pa = 0, pb = b.length - 1;
    var pairs = [];
    while (pa < a.length && pb >= 0) {
        if (a[pa] + b[pb] > sum ) {
            pb = pb - 1;
        } else if (a[pa] + b[pb] < sum) {
            pa = pa + 1;
        } else {
            pairs.push([a[pa], b[pb]]);
            pa = pa + 1;
            pb = pb - 1;
        }
    }
    return pairs;
}

// data for test
var arr1 = [-1, 1, 2, 3, 4, 5, 7, 9],
    arr2 = [5, 7, 10, 12, 13, 14, 15];
console.log(getSumPairs(arr1, arr2, 14))
console.log(getSumPairs(arr1, arr2, 15))

该算法是对数组a中的数据求和，并从不同端b。当数组排序时：

如果a[i] + b[j] < sum，a[i] + b[j-1]还是会不足sum，所以只需要增加i。

如果a[i] + b[j] > sum，a[i+1] + b[j]仍然会大于sum，所以只需要减少j即可。

因此，来自拖曳数组的所有元素只循环一次。对于a[N]和b[M]，复杂度为O(M + N)。

自己尝试 http://jsfiddle.net/9L4p1j3L/

function find (A1, A2, ans) {
  var a = [];
  for (var i = 0, len1 = A1.length; i < len1; i++) {
    var noToSearch = ans - A1[i];
    var secondIndex  = binarySearch(A2,noToSearch);
    if(secondIndex !=-1){
        a.push(i + ', ' + secondIndex );
    }
  }
  return a;
}
function binarySearch(A2,num){
 var index = -1;
  //write binary search algo to find the element in array A2
 return index;
}
相关文章：