查找两个数组之间的共同最小值

Question

我正在处理 Javascript 中的一个问题。寻找两个数组之间的共同最小值。但是，有人告诉我这可能不适用于某些值。问题是什么？

function cmp(a, b) { return a - b; }

function findMinimum(A, B) {
    var n = A.length;
    var m = B.length;
    A.sort(cmp);
    B.sort(cmp);
    var i = 0;
    for (var k = 0; k < n; k++) {
        if (i < m - 1 && B[i] < A[k])
            i += 1;
        if (A[k] == B[i])
            return A[k];
    }
    return -1;
}

Answer 1

这应该有效。只需将第一个替换if为while. 循环while遍历数组 B，直到找到大于 A 的最小元素的元素。然后，外循环for遍历 A 查找与 B 的当前元素匹配的任何元素，或者直到找到大于 A 的最小元素的元素。 B 的当前元素，重复该过程。

function cmp(a, b) {
  return a - b;
}

function findMinimum(A, B) {
  var n = A.length;
  var m = B.length;
  A.sort(cmp);
  B.sort(cmp);
  var i = 0;
  for (var k = 0; k < n; k++) {
    while (i < m - 1 && B[i] < A[k])
      i += 1;
    if (A[k] == B[i])
      return A[k];
  }
  return -1;
}

findMinimum([1,3,5,7], [0,0,1,4,9]);  // 1
findMinimum([3,5,7,9], [1,2,4,7,10]); // 7

Answer 2

让我们来，

A = [ 1, 3, 5, 7]
B = [ 0, 0, 1, 4, 6]

并运行您的循环。

你的脚本失败了。

正确的逻辑应该是，你要么增量i或k在1次迭代。不是都

我会做类似的事情，

for (var k = 0; k < n;) {
    if (A[k] == B[i])
        return A[k];

    if (i < m - 1 && B[i] < A[k])
        i += 1;
    else
        k += 1;
}