首页 > 试题广场 >

设计一个排行榜,有N条记录(记录结构:排名,用户名,积分),

[问答题]
设计一个排行榜,有N条记录(记录结构:排名,用户名,积分),积分大的排名靠前,需要提供一下操作:
1)
某一个用户积分发生变化的时候,更新排行榜数据结构
2)
使用用户名,获取用户排名
3)
获取第n 名用户名和积分
问题:
1) 当
 N=1000 时,请写出TopList 类中未完成的成员函数?
struct UserInfo
{
    string name;
    long score;
    bool operator<(const UserInfo& rhs)
    {
        1,______
    }
};
struct TopList
{
public:
    //刷新排行榜
    bool Refresh TopList(const UserInfo& user)
    {
        2,______
    }
    //根据用户名活的用户排名
    int GetRankByUserName(string& name)
    {
         3,______
    }
    //根据用户名次取得用户信息
    UserInfo* GetUserByRank(long rank)
    {
        4,______
    }
private:
    std::multiset items_;
}; 

2)当N=1000万时,设计排行榜的数据结构,和相关操作的算法?(伪代码表示)
问题(1):
讲道理如果是C++代码的话,这个应该运行不了的,因为这个重载<操作符的返回格式有问题,应该在函数尾巴上加上const,并且题目里没有声明multiset是什么类型,不过可以猜到是UserInfo类型,所以基于此,大致代码如下:
1.
return this->score < rhs.score;
2.
multiset<UserInfo>::iterator elm = items_.insert(user);
if (elm->name == user.name)
return true;
return false;
3.
multiset<UserInfo>::iterator begin = items_.begin();
multiset<UserInfo>::iterator end = items_.end();
for (int i = 1; begin != end; i++) {
if (begin->name == name)
return i;
begin++;
}
return -1;
4.
multiset<UserInfo>::iterator itr = items_.begin();
while (rank != 1) {
rank--;
itr++;
}
//原迭代器格式为静态指针:const UserInfo*
return (UserInfo*)&(*itr);


问题(2):
思路:可以采用分治思想
步骤:
1. 将1000w条数据拆分成每1w条为一组。
2. 对每个组内部进行快速排序,使每个分组内部有序。
3. 将不同的组之间进行归并排序,拼成完整数组。

几个坑需要注意一下:
1. multiest默认已经有序,从小到大排列,与set相比元素可以重复。题目中从大到小排列可以通过在定义的时候指定排序准则为greater来实现(然而本题中multiset定义不全,所以这个例子实现的其实是从小到大排列)
2. 实现对比较运算符的重载可以采用友元函数:
friend bool operator < (UserInfo u1, UserInfo u2) {
    return u1.score < u2.score;
}
然而题目中不能修改那部分,如果还要重载的话可以在函数尾端加上const:
bool operator < (const UserInfo& rhs)const {
    return this->score < rhs.score;
}
不同的实现方式参数列表也不一样,需要注意。
3. 对于multiset插入后,迭代器会指向插入的那个位置,所以可以通过比较值是否相等来判断成功(虽然我不知道检查一个总是可以成功插入的multiset的意义是什么)
4. 对于本题需要的索引号,使用Find方法来查找估计是不行的,所以我这自己实现了一下用迭代器遍历比较,如果数字很多的话查找应该会很费时间。
5. 对于返回UserInfo的部分,如果新建一个变量在GetUserByRank方法结束后其值会被释放,所以返回主函数后可能会出现string类型的数据丢失的问题。故采用对迭代器手动造型的方法来之间返回指针。

最后:以上都是我乱说的hhhh
编辑于 2019-10-12 17:39:30 回复(1)