https://leetcode.com/problems/design-twitter/description/
参考了这篇博客,非常巧妙
http://www.cnblogs.com/grandyang/p/5577038.html
方法是建立一个TreeMap,然后在getNewsFeed时,loop所有好友,然后对于每一个好友loop其twitter,最后放进一个size 10 的minheap里,minheap是用c++ map (java TreeMap) 实现的。为了把自己的twitter也loop到,自己需要follow自己。
注意:map的loop要加*, to access to individual elements
class Twitter {
unordered_map<int, unordered_set<int>> friends;
unordered_map<int, map<int, int>> tweets;
int cnt;
public:
/** Initialize your data structure here. */
Twitter() {
cnt = 1;
}
/** Compose a new tweet. */
void postTweet(int userId, int tweetId) {
follow(userId, userId);
tweets[userId].insert({cnt++, tweetId});
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
vector<int> getNewsFeed(int userId) {
map<int, int> top10;
for(int it_f : friends[userId]){
for(auto it : tweets[it_f]){
if(top10.size() < 10 || it.first > (*top10.begin()).first){
top10.insert(it);
}
if(top10.size() > 10) top10.erase(top10.begin());
}
}
vector<int> ret;
for(auto it = top10.rbegin(); it != top10.rend(); it++){
ret.push_back((*it).second);
}
return ret;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
void follow(int followerId, int followeeId) {
friends[followerId].insert(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
void unfollow(int followerId, int followeeId) {
if(followerId == followeeId) return;
friends[followerId].erase(followeeId);
}
};
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* vector<int> param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
*/