5

给定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]。

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

我的尝试如下。这里的操场。

有没有更有效（更快）的方法来实现这一目标？

希望有一个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]
4

3 回答 3

3

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

有一些事情可能会触发这样的功能：

  • 钠
  • 错误的限制
  • 重复的数字
  • 只有 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;
            }
        }
    }
}

（小提琴：http: //jsfiddle.net/kn2wz2sc/4/）

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

在 Mk2 中，我从 Casey 的计数匹配方法中获得了一些灵感，而不是每次从 0 到 n 进行检查，这使得它可以简化一些比较（并且由于 Casey 现在使用索引，这两种方法变得非常相似） . 在 Mk3 中，我进行了更多的微优化，急切地增加索引，使其不需要内部循环。

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

一个 jsperf 表明 Mk3 是迄今为止最快的方法：http://jsperf.com/sorted-intersect/5 （它仍然可以安全地防止重复和 NaN）。

于 2015-05-10T08:59:22.593 回答
2

这是另一种算法，其想法是我们计算看到每个数字的次数。一旦我们看到它arrs.length，我们就知道它在十字路口。如果它甚至从一个列表中丢失，它不在交叉点，我们可以跳到该列表中的下一个数字。事实证明要快得多！

这种方法会改变数组，但更容易阅读。

function intersection(arrs, limit) {
    var intersections = [];

    // Keep track of how many times we've seen the largest element seen so far.
    var largest = -Infinity;
    var count = 0;

    while (intersections.length < limit) {
        for (var i = 0; i < arrs.length; i++) {

            // Drop elements less than `largest`.
            while (arrs[i].length && arrs[i][0] < largest)
                arrs[i].shift();

            // Ignore repeated elements (not needed if you don't have repeated elements).
            while (arrs[i].length >= 2 && arrs[i][0] == largest && arrs[i][1] == largest)
                arrs[i].shift();

            // If we ran out of elements, we're done.
            if (!arrs[i].length)
                return intersections;

            // Look at the next element.
            var next = arrs[i].shift();
            if (next == largest)
                count++;
            else {
                count = 1;
                largest = next;
            }

            // Once we see it enough times, we can be sure it's in the intersection!
            if (count == arrs.length)
                intersections.push(largest);
        }
    }

    return intersections;
}

这种方法没有，但它更难阅读。

function intersection(arrs, limit) {
    var intersections = [];
    var indices = [];
    for (var i = 0; i < arrs.length; i++)
        indices[i] = 0;

    // Keep track of how many times we've seen the largest element seen so far.
    var largest = -Infinity;
    var count = 0;

    while (intersections.length < limit) {
        for (var i = 0; i < arrs.length; i++) {

            // Skip past elements less than `largest`.
            while (indices[i] < arrs[i].length && arrs[i][indices[i]] < largest)
                indices[i]++;

            // If we ran out of elements, we're done.
            if (indices[i] >= arrs[i].length)
                return intersections;

            // Look at the next element.
            var next = arrs[i][indices[i]++];
            if (next == largest)
                count++;
            else {
                count = 1;
                largest = next;
            }

            // Once we see it enough times, we can be sure it's in the intersection!
            if (count == arrs.length)
                intersections.push(largest);
        }
    }

    return intersections;
}
于 2015-05-10T09:16:46.017 回答
1

更快（但远不如其他答案快）：

function intersectMultiple(sortedArrays, limit) {
    var set = {}, result = [],
        a = sortedArrays.length,
        l = Math.max.apply(null, sortedArrays.map(function (a) {
            return a.length;
        })), i, j, c = 0, val;

    for (i = 0; i < l && c < limit; i++) {
        for (j = 0; j < a && c < limit; j++) {
            val = sortedArrays[j][i];
            if (!set.hasOwnProperty(val)) set[val] = 0;
            if (++set[val] === a) result[c++] = val;
        }
    };
    return result;
}

和

var s = [
    [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]
];

intersectMultiple(s, 2);

// [5, 10]

http://jsperf.com/intersect-multiple

于 2015-05-10T08:29:38.033 回答