用C++完成某种聊天工具,每个好友的id都是唯一的,当用户接收到信息后,如果会话窗口之前没有与该好友的聊天信息,则在通信列表里,会将新接收的消息的好友id置顶,如果会话窗口中已有与该好友的聊天信息,则将该好友的id移动到通讯列表的顶端。请根据要求实现该功能。 输入:第一行为整数N,代表有N组测试数据,接下来的N组测试中,第一行为整数T,代表有T条通讯,第二行有T个整数,按时间先后顺序表示接收到讯息的好友id。 输出:按照通讯列表从上到下的顺序输出好友id,每个id以空格分隔。 样例输入: 3 5 1 2 3 4 5 6 1 2 3 3 2 1 7 1 5 2 2 1 7 1 样例输出: 5 4 3 2 1 1 2 3 1 7 2 5
时间: 2024-02-27 09:58:35 浏览: 70
以下是代码实现:
```c++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n;
cin >> n;
while (n--) {
int t;
cin >> t;
vector<int> ids(t);
unordered_map<int, int> index;
for (int i = 0; i < t; i++) {
cin >> ids[i];
if (index.find(ids[i]) == index.end()) {
// 如果该好友id没有出现过,将其插入到通信列表的顶端
index[ids[i]] = i;
} else {
// 如果该好友id已经出现过,将其移动到通信列表的顶端
int pos = index[ids[i]];
for (int j = pos; j < i; j++) {
index[ids[j]] = j + 1;
ids[j] = ids[j + 1];
}
ids[i - 1] = ids[i];
index[ids[i]] = i - 1;
}
}
// 输出通信列表
for (int id : ids) {
cout << id << " ";
}
cout << endl;
}
return 0;
}
```
代码思路:
对于每组测试数据,我们先读入该组测试数据中的所有好友id,然后使用一个哈希表 `index` 记录每个好友id在通信列表 `ids` 中的位置。
接着,我们遍历每个好友id,如果该好友id没有出现过,则将其插入到通信列表的顶端,并更新 `index` 中对应的位置;如果该好友id已经出现过,则将其移动到通信列表的顶端,并更新 `index` 中所有好友id的位置。
最后,我们按照通信列表从上到下的顺序输出好友id即可。
注意:由于每个测试数据的好友id不同,因此我们需要在每组测试数据中都新建一个哈希表 `index`。
阅读全文