给定 N 个排序的整数数组(无重复项)，我想计算它们交集中的第一个 limit 个整数。

例如，给定以下数组:

[2, 5, 7, 8, 10, 12, 13, 15, 20, 24]
[3, 4, 5, 6, 9, 10, 11, 17, 20]
[1, 2, 3, 5, 6, 10, 12, 20, 23, 29]

交集是[5, 10, 20]，所以如果limit = 2，结果应该是[5, 10] .

给定的数组不应该被改变。

我的尝试如下。 Playground here.

是否有更有效(更快)的方法来实现这一点？

将不胜感激jsperf比较。

function intersection(sortedArrays, limit) {
  var arraysCount = sortedArrays.length;
  var indices = sortedArrays.map(function(array) { return 0; });
  var values, maxValue, valuesAreSame, reachedEnd, i, result = [];

  while (true) {
    reachedEnd = indices.some(function(index, i) {
      return index === sortedArrays[i].length;
    });

    if (reachedEnd) {
      return result;
    }

    values = sortedArrays.map(function(array, i) { return array[indices[i]]; });
    valuesAreSame = values.every(function(value, i) { return value === values[0]; });

    if (valuesAreSame) {
      result[result.length] = values[0];

      if (result.length === limit) {
        return result;
      }

      for (i = 0; i < arraysCount; i++) {
        indices[i]++;
      }
    } else {
      maxValue = Math.max.apply(null, values);

      for (i = 0; i < arraysCount; i++) {
        if (values[i] < maxValue) {
          indices[i]++;
        }
      }  
    }  
  }
}

console.log(intersection([[0, 3, 8, 11], [1, 3, 11, 15]], 1));
// => [3]

最佳答案

第一个挑战是使函数正确。一旦正确，我们就可以担心速度了。

有一些事情可能会像这样使函数失败:

• NaN
• 错误限制
• 重复的数字
• 只有 1 个输入数组(或根本没有)

您的原始函数可以处理重复的数字，例如 [[9,9,9,9],[9,9,9]]，但如果任何值为 NaN，就会陷入无限循环，并处理一个限制0 就好像根本没有限制一样。

这是我的 (Mk3) 尝试:

function intersection( arrs, limit ) {
    var result = [], posns = [];
    var j, v, next, n = arrs.length, count = 1;
    if( !n || limit <= 0 ) {
        return result; // nothing to do
    }
    if( n === 1 ) {
        // special case needed because main loop cannot handle this
        for( j = 0; j < arrs[0].length && result.length < limit; ++ j ) {
            v = arrs[0][j];
            if( v === v ) {
                result.push( v );
            }
        }
        return result;
    }
    for( j = 0; j < n; ++ j ) {
        if( !arrs[j].length ) {
            return result; // no intersection
        }
        posns[j] = 0;
    }
    next = arrs[n-1][0];
    ++ posns[n-1];
    while( true ) {
        for( j = 0; j < n; ++ j ) {
            do {
                if( posns[j] >= arrs[j].length ) {
                    return result; // ran out of values
                }
                v = arrs[j][posns[j]++];
            } while( v < next || v !== v );

            if( v !== next ) {
                count = 1;
                next = v;
            } else if( (++ count) >= n ) {
                result.push( next );
                if( result.length >= limit ) {
                    return result; // limit reached
                }
                if( posns[j] >= arrs[j].length ) {
                    return result; // ran out of values
                }
                next = arrs[j][posns[j]++];
                count = 1;
            }
        }
    }
}

( fiddle :http://jsfiddle.net/kn2wz2sc/4/)

这与您的原始方法的工作方式大致相同，但有几处优化。它总是知道下一个要查找的数字，并会快速遍历每个数组，直到找到一个至少有那么大的数字。如果数字太大，它将更新它正在寻找的数字。

在 Mk2 中，我从 Casey 的计算匹配项的方法中获得了一些灵感，而不是每次都从 0-n 检查，这允许它缩短一些比较(并且由于 Casey 现在使用索引，这两种方法都成为非常相似)。在 Mk3 中，我做了一些微优化，急切地增加索引，这样它就不需要内部循环了。

这对于我上面列出的所有标准都是安全的(它忽略 NaN，因为 NaN!=NaN 因此永远不会在交集)，不限于数字，一旦达到任何限制就会快速退出。

jsperf 显示 Mk3 是迄今为止最快的方法:http://jsperf.com/sorted-intersect/5 (并且对于重复项和 NaN 仍然是安全的)。

关于javascript - N 个排序整数数组的交集有限制，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30148854/