javascript - 计算通过三个数组的最短路径

Question

我有三个数组，也可能是n个。让我们现在拿三个。他们有这样的值(value)观:-

Array1=[143, 181];
Array2=[41, 153, 241];
Array3=[22, 67, 131, 190];

我想找出这三个数组的那些元素，谁的差值最小。就像在这种情况下，143,153,131 具有最小差异。

Answer 1

假设您没有大量数组，这里有一个解决方案，计算(和存储)所有路径:

// First let's use a sensible structure
var arrays = [Array1, Array2, Array3];

// Then, let's compute all possible paths
var paths = arrays[0].map(function(v){ return [v] });
for (var i = 1; i<arrays.length; i++) {
   var arr = arrays[i];
   for (var j=paths.length; j--; ) {
      var newPaths = arr.map(function(v){
        return paths[j].concat(v);
      })
      newPaths.unshift(j,1);
      [].splice.apply(paths, newPaths);
   }
}

// Now, let's just take the shortest one
var shortestDistance = Infinity,
    shortestPath = null;
paths.forEach(function(path){
  var distance = 0;
  for (var i=1; i<path.length; i++) {
    distance += Math.abs(path[i]-path[i-1]);
  }
  if (distance<shortestDistance) {
    shortestDistance = distance;
    shortestPath = path;
  }
});

// Finally, let's log the result
console.log(shortestDistance, shortestPath);

记录

32
[143, 153, 131]