javascript - 查找未使用的组合

Question

找到数组中不存在的组合的快速方法是什么？

例如，我有点列表:[1, 2, 4, 9]

我有一个连接列表 [[1,2], [1,4], [1,9], [2,4], [4,9]]

因此此列表中缺少的连接是 [2,9]。因为有一个要求:每个整数都必须连接到一个更大的整数。

var points = [1, 2, 4, 9];
var connections = [[1,2], [1,4], [1,9], [2,4], [4,9]];

var missing = [];
for(i = 0; i < points.length; i++){
  for(j = i + 1; j < points.length; j++){
    var found = false;
    for(var a = 0; a < connections.length; a++){
        if(connections[a][0] == points[i] && connections[a][1] == points[j]){
        found = true;
        break;
      }
    }
    if(!found) missing.push([points[i], points[j]]);
  }
}

console.log(missing);

上面的代码可以工作，但是 for 循环的数量让我觉得它相当慢。有没有更快的方法来做到这一点？查看jsfiddle

Answer 1

通过对数组进行排序，可以用2个嵌套来完成。排序需要 O(n log n)，而循环基本上是 O(n ^ 2)。

var points = [1, 2, 4, 9];
var connections = [
  [1, 2],
  [1, 4],
  [1, 9],
  [2, 4],
  [4, 9]
];

connections.sort();

var missing = [];
var currentIndex = 0;
for (var i = 0; i < points.length; i++) {
  for (var j = i + 1; j < points.length; j++) {
    if (connections[currentIndex][0] == points[i] && connections[currentIndex][1] == points[j]) {
      currentIndex++;
    } else {
      missing.push([points[i], points[j]]);
    }
  }
}

console.log(missing);