我有三个数组,或者可能是n个。现在我们先考虑三个数组。
它们的值如下:
Array1=[143, 181];
Array2=[41, 153, 241];
Array3=[22, 67, 131, 190];
我想找到这三个数组中差距最小的元素,就像在这个例子中,143、153和131的差距最小。
我有三个数组,或者可能是n个。现在我们先考虑三个数组。
它们的值如下:
Array1=[143, 181];
Array2=[41, 153, 241];
Array3=[22, 67, 131, 190];
假设您没有大量的数组,这里提供一种解决方案,即计算(和存储)所有路径:
// 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]
* (root)
/ \
143 181
/ | \ / | \
41 153 241 41 153 241
/|\/|\ /|\ /|\/|\ /|\
........ descendants from 3rd array
function recursiveMinDiff(arrays)
{
var minSoFar, minNodes;
function computeMinDiff(values)
{
var i, vs, total;
vs = values.slice();
vs.sort(function (a,b) { // ascending order
return a - b;
});
total = 0;
for (i = 0; i < vs.length - 1; i++)
{
total += vs[i + 1] - vs[i]; // always non-negative
}
return total;
}
function mindiff(arrays, stack)
{
var i, diff, level;
level = stack.length;
if (level === arrays.length) // this is a leaf
{
diff = computeMinDiff(stack);
if (diff < minSoFar)
{
minSoFar = diff; // side-effect on min*
minNodes = stack.slice(); // clone array
}
return;
}
for (i = 0; i < arrays[level].length; i++)
{
stack.push(arrays[level][i]);
mindiff(arrays, stack);
stack.pop();
}
}
minSoFar = Number.MAX_VALUE;
minNodes = [];
mindiff(arrays, []);
return minNodes;
}