找到两个数组之间的公共最小值

I am working on a problem in Javascript. Finding common minimum value between two arrays. However, I have been told that this might not work on some values. What is the issue?

我正在研究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;
}

3 个解决方案

#1

I'd suggest changing your methodology here. Sorting both of the arrays at the beginning is expensive. Find the intersection set of two arrays and then sort it and return its mimimum value, that's all.

我建议你在这里改变你的方法。在开始时对两个阵列进行排序是很昂贵的。找到两个数组的交集，然后对其进行排序并返回其最小值，即全部。

#2

Let's take,

让我们来，

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

and run through your loop.

并贯穿你的循环。

Your script fails.

你的脚本失败了。

The correct logic should be, you either increment i or k in 1 iteration. Not both

正确的逻辑应该是，您可以在1次迭代中递增i或k。不是都

I would do something like,

我会做的事情，

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;
}

#3

This should work. Just replace the first if with a while. The while loop loops through array B till it finds an element which is greater than the minimum element of A. Then the outer for loop loops through A to find any element that matches the current element of B or till it reaches an element that is greater than the current element of B, where the process repeats.

这应该工作。只需用一段时间替换第一个。 while循环遍历数组B，直到找到一个大于A的最小元素的元素。然后外部for循环遍历A以找到与B的当前元素匹配的任何元素，或者直到它到达更大的元素比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

#1