javascript - 比较数组以检查序列

假设我们有以下嵌套数组集：

var array = [
              [a,b,c],
                  [c,d,e],
                      [e,f,g],
                          [g,h,i]
            ]

如果我们以[a,b,c]开头并想查找以c开头的任何嵌套数组，并且如果有的话，将该数组的索引2处的元素推到已经包含c的新数组中，可以编写以下代码：

var container = [];
container.push(array[0][2]);

for (var i = 0; i < array.length; i++) if (array[0][2] === array[i][0]) container.push(array[i][2])

因此，container最终将成为[c,e]。

很简单。

但是，如果我们现在还想检查e是否与任何其他array[i][0]匹配怎么办？依此类推，直到我们检查了整个array并得到以下数组：[c,e,g,i]。

我要尝试做的是查看给定数组的最后一个元素是否匹配任何其他数组的第一个元素；然后，收集该数组中的最后一个元素，并检查该元素是否与任何其他嵌套数组中的第一个元素匹配。

因此，如果我们以i开头，则最终会以[i]结尾。

如果我们从元素g开始，我们将以[g,i]结尾。

现在，我正在使用嵌套的for循环和if/else语句，如下所示：

for (var i = 0; i < array.length; i++) {
  if (element === array[i][0]) {
    container.push(array[i][2]);
    for (var ii = 0; ii < array.length; ii++) {
      if (array[i][2] === array[ii][0]) {
        container.push(array[ii][2]);
        for (var iii = 0; iii < array.length; iii++) {
          if (array[ii][2] === array[iii][0]) {
            container.push(array[iii][2])
            for (var iiii = 0; iiii < array.length; iiii++) {
              if (array[iii][2] === array[iiii][0]) {
                container.push(array[iiii][2])
              }
            }
          }
        }
      }
    }
  }
}

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

我应该提到，数组的初始集合可以包含重复的值，例如：[ [a,b,c], [a,b,c], [g,h,i], [x,y,z] ]或[ [a,b,c], [a,b,c], [c,d,e], [x,y,z] ]。

要启动，我注意到我的当前方法会吐出不想要的结果，例如上面第二种情况下的[c,e,c,e]而不是简单的[c,e]。

改用数字来考虑可能会更容易：

var array = [
              [2,n,4],
                  [4,n,6],
                      [6,n,8],
                          [8,n,10]
            ]

如果起始值为4，则应将array[1][2]或6推到container，然后尝试将array[1][2]或6匹配到array[i][0]。因此，容器将总是最终成为2,4,6,8或6,8或4,6,8等序列。

最佳答案

记录一下，这就是@zerkms的含义，即创建一个单独的索引，即字母到字母的映射：

var stringArray = [
  ['a', 'b', 'c'],
  ['c', 'd', 'e'],
  ['c', 'd', 'e'],
  ['e', 'f', 'g'],
  ['g', 'h', 'i']
];
var numberArray = [
  [2, 3, 4],
  [4, 5, 6],
  [6, 7, 8],
  [8, 9, 10]
];

// this implementation assumes there are no cycles or divergent branches
function chainSearch(array, start) {
  var container = [start];
  var map = new Map();
  var index, inner, first, last;
  var current = start;

  // construct an element-to-element map in O(N)
  for (index = 0; index < array.length; index++) {
    inner = array[index];
    first = inner[0];
    last  = inner[inner.length - 1];

    if (!map.has(first)) {
      map.set(first, last);
    }
  }

  // assuming the chain is length L
  // whole implementation is ~O(N+L) instead of O(N^L)
  while (map.has(current)) {
    current = map.get(current);
    container.push(current);
  }

  return container;
}

console.log(chainSearch(stringArray, 'c').join());
console.log(chainSearch(stringArray, 'g').join());

console.log(chainSearch(numberArray, 2).join());
console.log(chainSearch(numberArray, 6).join());

关于此实现的好处是，即使演示使用基元（字符串和数字），该方法也适用于非基元的嵌套数组，并假设您要测试对相同对象而不是相同副本的引用。

关于javascript - 比较数组以检查序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44512103/