Finding common minimum value between two arrays

问题:

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?

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

回答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

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.

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