改善当前时间复杂度

Question

我在一次采访中遇到了这个问题。我能够使用嵌套循环方法来做到这一点。我想知道是否有更好的方法可以做到这一点？

给定的API-getFriends（person）：它返回该人的朋友数。-getItems（person）：它返回该人购买的物品。

问题：返回一个人的朋友从购买最多到购买最少的物品的列表。

function getList(person)
{
    var itemsMap = {};
    var friends = getFriends(person);
    for(var i = 0 ; i < friends.length; i++)
    {
       var items = getItems(friends[i]);
       for(var j = 0 ; j < items.length; j++)
       {
         if(!itemsMap[items[j]])
             itemsMap[items[j]] = 1;
         else
             itemsMap[items[j]] = itemsMap[items[j]] + 1;
       }
    }

    var res = [];

    itemsMap.sort();

    for(item in itemsMap)
        res.push(item);


    return res;
}

Answer 1

您的代码的瓶颈不是双循环。您必须仔细检查所有项目，这正是您要做的。

瓶颈正在排序，可能是O((n*m)log(n*m))-其中n是“朋友”的数量，m是每个朋友的平均物品数量。

但是，在O(n*m)中，可以通过选择明智的排序方式（例如bucket sort）或在构建itemsMap时甚至对元素进行排序来完成。

之所以能获得比常规案例排序更好的性能，是因为每个项目的大小受到限制，并且所有这些项目的总和最多为n*m。