背景：最近在面试，被问到一个租房网站项目中用到的一个分页算法，心里明白但却呜噜呜噜说不清楚，可能自己表达能力有限，且项目年代久远，故在此梳理一遍。
问题描述：在租房网站中，我们想要在一页显示多个房东的房源，避免出现一页出现很多重复房东的房源，比如说房东A有4套房子，编号分别为h1-h10，而我们的页面一页能显示4套房子，那我们就要实现一种算法，在分页的时候保证一页只出现一个房东A的房源，除非在显示完数据中所有的房子后，页面还没有被填满，那就再把A的第二套填入该页。
举例：假如此时我们有如下这张数据表，我们一页能展示4个房源
首先，把所有数据加入未分配数据表，我们创建一个结果的数组，叫做res，然后设置一个临时页tmp用来表示当前正在装填的页面，再设置一个p指针用来遍历数据
我们在往页面装填当前数据的时候，先判断该数据在页面tmp中是否存在，
1.如果临时页中不存在该数据，则把这条装入页面（tmp.insert(*p)），并从未分配数据表中删除该数据
2.否则，跳过该数据，查看下一条数据（p++）
重复上一步知道页面装满或者遍历到了最后一条数据
如果页面已满，把临时页面放入res中，清空临时页，p指向数据的开头，准备用来填装新的一页了
如果已经遍历到了最后一条页面还没有装满，则再从头遍历数据，按顺序把数据放进去，并从未分配数据表中删除该数据，直到装满页面或者没有数据了（这种情况表明数据太少，只好凑合让重复数据显示在同一页了，假如数据只有A的4个房间，那没办法，我们只能在第一页把它们全展现出来了）
对于上面的数据表，正确的分页应该如下所示：
该算法的核心是用一个链表维护剩余未被分配的数据，当遍历链表分配数据的时候，该数据分配完后，要从未分配数据表中删除，如果用一个数组或维护该表，则删除该数据后，每一项数据都要往前移动一位，非常浪费时间，用链表的话并不影响整体结构，删除的效率为O(1)，
输入：房源信息info和页面最大容量n
输出：分出来的所有页面
此处简化一下输入和输出格式
房源信息info是一个string的数组，房东id和房源id用逗号隔开，n表示一个页面的最大容量
{
{"1,20"}//1是房东id，20是房源id
{"1,20"}
{"1,20"}
{"1,20"}
......
}
输出用一个字符串数组的数组表示：
{
{//第一页,每一页有n条房源信息
{"1,5"}//第一页的第一条房源，房东id为1，房源id为5
{"2,6"}//第一页的第2条房源，
{"3,21"}
{"4,22"}
}
{//第二页
{"1,10"}//第2页的第1条房源
{"3,7"}
{"5,8"}
{"3,9"}
}
......
}
该算法用c++写出来如下所示：
vector<vector<string>> getPage(vector<string> infos,int n){
list<string> l;
vector<vector<string>> res;
for(string s:infos){
l.push_back(s);
}
while(!l.empty()){
auto it=l.begin();
vector<string> page;
set<int> st;
while(it!=l.end()&&page.size()<n){
string tmp=*it;
int len=tmp.find_first_of(',');
cout<<tmp.substr(0,len)<<endl;
int id=stoi(tmp.substr(0,len));
if(st.find(id)!=st.end()){//重复
it++;
continue;
}
page.push_back(tmp);
it=l.erase(it);
st.insert(id);
}
//补全
it=l.begin();
while(it!=l.end()&&page.size()<n){
string tmp=*it;
int len=tmp.find_first_of(',');
int id=stoi(tmp.substr(0,len));
page.push_back(tmp);
it=l.erase(it);
st.insert(id);
}
res.push_back(page);
for(string p:page){
cout<<p<<endl;
}
}
return res;
}
