N个已排序的整数数组的交集（带限制）

Question

N个已排序的整数数组的交集（带限制）

javascriptarraysalgorithmintersectionset-intersection

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]

- Misha Moroshko

1

是的，这被称为N路合并（或k路合并），当大小达到限制时，简单地停止合并。这里有一个链接提供了一个相当好的概述，说明如何实现它。虽然它使用文件而不是数组，但原理是相同的。 - Nuclearman

3个回答

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

- Casey Chu

这个速度很快，但它不能一致地处理 NaN: ([[0, 3, 4, 0/0, 11], [1, 3, 11, 15]], 8) 会产生 "3"，而 ([[0, 3, 0/0, 11], [1, 3, 11, 15]], 8) 会产生 "3,11"。 - Dave

@Casey 很好，谢谢！我忘了提到数组不应该被改变，所以如果你复制它们，这应该被视为算法时间的一部分。你介意更新jsperf吗？ - Misha Moroshko

更新后包括一个不改变元素的版本。至于NaN问题，它们被认为是排序好的整数数组，因此不应该有NaN。 - Casey Chu

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

- Tomalak

您所应用的限制过于严格：[2, 5, 7, 8, 10, 12, 13, 15, 20, 24, 29]，[3, 4, 5, 6, 9, 10, 11, 17, 20, 29]，[1, 2, 3, 5, 6, 10, 12, 20, 23, 29]并未返回29。 - Dave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dave · Accepted Answer

第一个挑战是确保函数的正确性。一旦正确，我们可以考虑速度的问题。

有几个因素可能会导致这样的函数出错:

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 安全）。