首页 > 试题广场 >

设计一个排行榜，有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万时，设计排行榜的数据结构，和相关操作的算法？（伪代码表示）

SuperAidenGreen

问题（1）：

讲道理如果是C++代码的话，这个应该运行不了的，因为这个重载<操作符的返回格式有问题，应该在函数尾巴上加上const，并且题目里没有声明multiset是什么类型，不过可以猜到是UserInfo类型，所以基于此，大致代码如下：

return this->score < rhs.score;

multiset<UserInfo>::iterator elm = items_.insert(user);
if (elm->name == user.name)
return true;
return false;

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)