题目描述

设计一个简易版今日头条，有以下4个功能：

1. 发头条，postToutiao(int userId, int toutiaoId)
2. 关注别人，follow(int followerId, int followeeId)
3. 取消关注别人，unfollow(int followerId, int followeeId)
4. 查看10条最近的头条，包括自己发的和我关注的人发的头条，vector<int> getNewsFeed(int userId)

Example

Toutiao toutiao = new Toutiao();
// 用户1发了一条头条，id是5
toutiao.postToutiao(1, 5);
// 查看用户1最近的头条，只有5 -> [5].
toutiao.getNewsFeed(1);
// 用户1关注了用户2
toutiao.follow(1, 2);
// 用户2发了一条头条，id是6.
toutiao.postToutiao(2, 6);
// 查看用户1最近的头条，包括6和5 -> [6, 5].
// 6在5前面，因为6比5发得晚.
twitter.getNewsFeed(1);
// 用户1取消关注用户2.
twitter.unfollow(1, 2);
// 查看用户1最近的头条，只有5 -> [5],
// 因为用户1没有关注用户2.
twitter.getNewsFeed(1);

这道题流程听起来有点复杂，但是没有涉及很难的算法，只要用好几个数据结构，即可达到比较好的算法性能。

设计数据结构

1. 首先，为了实现头条的排序，需要为头条打上时间戳，因此，存储头条用到pair，即pair<int, int>，第一个int存时间戳，第二个存头条id
2. 然后，要建一张表，记录每个用户发的头条，为了快速索引到用户，则用到hash map，用户id作为key，头条作为value，即unordered_map<int, vector<pair<int, int>>>
3. 另一张表，记录每个用户关注的人，由于关注的人不能重复，所以还要用到集合unordered_set，即unordered_map<int, unordered_set<int>> follower_map
4. 查看最近10条头条时，为了方便排序，用一下优先级队列priority_queue

C++代码

有了上面的数据结构，就可以开始写代码了。

首先，定义一个类，把成员变量和接口封装起来，在构造函数中进行简单的初始化：

发头条，很简单，构造一个pair，然后塞进feed_map里即可，新发的头条要放在最前面，这里用到的cur_feed_id就是之前提到的时间戳，每增加一条，则加1，用于头条的排序

关注，很简单，把要关注的人的id塞进map里即可，但是这里有一个case----关注自己，是不允许滴。。。

取消关注，简单，把id从map中擦掉即可。

查看最近10条头条，相对复杂了，我们先看下这里面用到的优先级队列的定义，定义一个cmp结构体，实现优先级队列中pair的排序，新的在队尾，旧的在队首：

下面是函数的实现，定义一个优先级队列用于存放结果，首先遍历自己发的头条，往优先级队列里面塞，新发的头条会自己跑到队尾，如果队列长度不到10，就直接塞，如果超过了，塞完后，要把队首的（最旧的）pop出去。

由于发头条时，已经将头条排好序了，所以遍历时，一旦遇到比队首还旧的，即可停止遍历。

遍历关注的人发的头条，与遍历自己发的头条，流程一样。

最后将priority_queue里面的头条放到vector中，前后顺序翻转一下，即可返回。

复杂度

发头条、关注和取关 的时间复杂度都是O(1)，查看最近头条的时间复杂度是O(N)，N为自己+关注的人发的所有的头条数。

参考资料：

Leetcode 第355题, https://leetcode.com/problems/design-twitter/