c++ - 在我的 friend 圈中找到最受欢迎的点赞

Question

我正在研究一种在我的 friend 网络中找到最受欢迎的点赞的方法。 “在我的 friend 圈中最受欢迎”的定义是“我的 friend 点赞数最多”。

假设每个 friend 都有一个唯一的id，并且有一些喜欢的页面。因此，给定一组这样的 friend ，我想找到最多 friend 喜欢的人，以及还有喜欢这个东西的 friend 。本质上，我想展示类似“您的 friend X、Y 和 Z 喜欢这个”的内容。

我的第一个解决方案是使用 Map(用于存储反向映射:like->set)和 Priority Queue(用于查找前 N 个)。这是我的算法(使用 C++ STL):

map< like, set<friend> > like2friendsMap;
for each friend {
  for each like {
    like2friendsMap[like].insert(friend); //populate the map
  }
}

priority_queue< pair<like, int> > pq;
for each like in like2friendsMap {
  int count = like2friendsMap[like].size(); //no. of friends who like this or "popularity"
  pq.push(like, count); //count is the priority
}

map< like, set<friend> > result
for i in 1 to N { //N is how many popular items I want
   result = pq.top();  //gives me the element with highest priority (most popular like)
   pq.pop();
}

由于 STL 在内部使用红黑树来实现映射，并使用最小/最大堆来实现优先级队列，所以这种方法对我来说似乎非常快。但是如果我有 100 个 friend 并且每个 friend 都有 100 个赞，那么内存使用量将是巨大的。当然，不是存储整个对象，我应该使用 friend id 和 like id 进行所有计算，这将大大减少内存使用量。

还有哪些算法或数据结构可以用来提高效率(提高速度，减少内存)？出于某种原因，我无法针对每个点赞存​​储 friend 列表，它必须在运行时计算。我正在使用 C++ 开发它，因此使用 STL 或 boost 的解决方案会更好。

Answer 1

create an integer list allPages which can be referenced by page
initialize it with 0
for every friend f
{
    for every page p liked by f
    {
        allPages[p]++;
    }
}
get the maximum of the allPages[p]

如果P是页数，那么它的空间复杂度就是O(P)。

如果F 是 friend 的数量，L 是每个人喜欢的平均页面。那么它的时间复杂度就是O(F*L)。因此，即使您再次遍历所有 friend 以检查谁都喜欢该页面，也不会增加太多复杂性。

O(F*L) + O(F) would remain O(F*L)

我认为最好再次迭代而不是存储 friend 。

或者您可以存储页面的反向引用本身。也就是说，对于每个页面，存储喜欢的 friend 列表。这不会占用太多空间，而且会以最小的复杂性完成您的工作。