0

假设我有以下 3 个数组，它们按升序排序exercisedateandtime：

var listA = [
  {name: "Mike", exercisedateandtime: 1299233593000, exercise: "Jumping Jacks"}, 
  {name: "Mike", exercisedateandtime: 1299237012000, exercise: "Running"}
];

var listB = [
  {name: "Charles", exercisedateandtime: 1299233712000, exercise: "Swimming"},
  {name: "Charles", exercisedateandtime: 1299233831000, exercise: "Swimming"},
  {name: "Charles", exercisedateandtime: 1299240620000, exercise: "Swimming"}
];

var listC = [
{name: "William", exercisedateandtime: 1299237320000, exercise: "Fishing"},
{name: "William", exercisedateandtime: 1299237611000, exercise: "Motor Boating"},
{name: "William", exercisedateandtime: 1299305420000, exercise: "Cycling"}
];

合并这些列表以使我得到的结果数组listD也按升序排序的最有效方法是exercisedateandtime什么？是否可以创建一个接受任意数量数组的函数？（注意：虽然提供的样本很小，但理想的方法应该是处理大型列表。）

var listD = [
{name: "Mike", exercisedateandtime: 1299233593000, exercise: "Jumping Jacks"},
{name: "Charles", exercisedateandtime: 1299233712000, exercise: "Swimming"},
{name: "Charles", exercisedateandtime: 1299233831000, exercise: "Swimming"},
{name: "Mike", exercisedateandtime: 1299237012000, exercise: "Running"},
{name: "William", exercisedateandtime: 1299237320000, exercise: "Fishing"},
{name: "William", exercisedateandtime: 1299237611000, exercise: "Motor Boating"},
{name: "Charles", exercisedateandtime: 1299240620000, exercise: "Swimming"},
{name: "William", exercisedateandtime: 1299305420000, exercise: "Cycling"}
];
4

4 回答 4

3 
var listD = listA.concat(listB, listC).sort(function(a, b) {
    return a.exercisedateandtime - b.exercisedateandtime
});
于 2013-06-27T04:12:50.507 回答
1

这似乎只是对普通合并排序中合并的轻微改编（在 O(n) 中运行）。基本上，它的工作原理是您不断查看每个列表的开头，并将最大的最小的一个附加到新列表中，这对于三个列表的工作方式完全相同。所以这是来自 Aadit 解决方案的代码（与我的算法相同），但每个人似乎都在投票赞成一个比这个解决方案慢得多的解决方案，我想采取行动，所以 OP 最终不会使用它在他的代码中。

function merge(key) {
    var length = arguments.length, lists = [], newlist = [];
    for (var i = 1; i < length; i++) lists.push(arguments[i].slice());

    while (length = lists.length) {
        var min = Infinity;

        for (var i = 0; i < length; i++) {
            var list = lists[i];
            var value = list[0][key];

            if (value < min) {
                var index = i;
                min = value;
            }
        }

        var list = lists[index];
        newlist.push(list.shift());
        if (!list.length) lists.splice(index, 1);
    }

    return newlist;
}

现在您可以按如下方式合并列表：

var listD = merge("exercisedateandtime", listA, listB, listC);

基本上它的工作原理是获取一个列表列表和它应该排序的键，在这种情况下exercisedateandtime。然后它一直在寻找所有列表的最小前面元素，直到没有剩下的列表（while 循环有点棘手，因为它=返回的值是它设置lists为 0 时的值，它变为 false）。此合并适用于任意数量的列表，即使它们的大小不同。假设列表大小足够大以使列表的数量可以忽略不计，该算法在 O(n) 中运行。

编辑：在列表数量非常大的极其不理想的情况下，这里不是这种情况，因为只有三个列表，并且每个列表的大小都很小，最好做一个合并列表的解决方案就像在合并排序中一样，一次 2 个。可以通过检查列表的数量来调整代码来执行此操作，但是编写代码需要做更多的工作。我还会再重复一次，原来的问题是针对 3 个列表的，所以它可以正常工作。

这是我能找到的最理想的n 路合并的链接

于 2013-06-27T04:16:18.493 回答
1

确实是的。试试这个：

function merge(key) {
    var length = arguments.length, lists = [], newlist = [];
    for (var i = 1; i < length; i++) lists.push(arguments[i].slice());

    while (length = lists.length) {
        var min = Infinity;

        for (var i = 0; i < length; i++) {
            var list = lists[i];
            var value = list[0][key];

            if (value < min) {
                var index = i;
                min = value;
            }
        }

        var list = lists[index];
        newlist.push(list.shift());
        if (!list.length) lists.splice(index, 1);
    }

    return newlist;
}

现在您可以按如下方式合并列表：

var listD = merge("exercisedateandtime", listA, listB, listC);

在此处查看演示：http: //jsfiddle.net/b8WdW/2/

于 2013-06-27T04:39:47.263 回答
0

小提琴

基本上我在对它们进行排序之前先合并了数组。因此，即使您的数组未排序，这也应该有效。

var listD = listB.concat(listA, listC);
console.log(listD);
listD.sort(function (a, b) {
return a.exercisedateandtime - b.exercisedateandtime
});
console.log(listD);
于 2013-06-27T04:25:04.607 回答