数据结构与算法实验2020夏第二批（中国石油大学） PA9题解报告——重名剔除(Deduplicate)

目录

题目描述题目分析编码实现

一、题目描述

1. 描述

Epicure先生正在编撰一本美食百科全书。为此，他已从众多的同好者那里搜集到了一份冗长的美食提名清单。既然源自多人之手，其中自然不乏重复的提名，故必须予以筛除。Epicure先生因此登门求助，并认定此事对你而言不过是“一碟小菜”，相信你不会错过在美食界扬名立万的这一良机。

2. 输入

第1行为1个整数n，表示提名清单的长度。以下n行各为一项提名。

3. 输出

所有出现重复的提名（多次重复的仅输出一次），且以其在原清单中首次出现重复（即第二次出现）的位置为序

4. 例

//输入 10 brioche camembert cappelletti savarin cheddar cappelletti tortellni croissant brioche mapotoufu //输出 cappelletti brioche

5. 限制

1 < n < 6 * 10^5 提名均由小写字母组成，不含其它字符，且每项长度不超过40 时间：2 sec 空间：256 MB

6. 提示

散列

二、题目分析

代码实现

利用hash存储并快速找到字符串，并在存储时记录该字符串出现的次数，如果是第二次出现就输出一下。

复杂度分析：

时间复杂度：随字符串hash值冲突程度而定空间复杂度：$O(n)$

三、编码实现

说明： 下述代码全部为【数据结构与算法实验 OJ 平台】提交过的代码。

#include <cstring> #include <iostream> using namespace std; const int MAXSIZE = 6e5 + 5; char str[50]; typedef struct node { char val[50]; int cnt; node() { cnt = 0; } node *next; } * Node; Node nodeList[MAXSIZE]; int main() { int moddle = 6e5 - 10, p = 13331, n, length; long long int hight = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { hight = 0; scanf("%s", str); length = strlen(str); for (int j = 0; j < length; j++) { hight = (hight * p % moddle + (str[j] - 'a' + 1)) % moddle; } node *current = nodeList[hight]; int flag = 0; if (nodeList[hight] == NULL) nodeList[hight] = new node; while (NULL != current) { if (strcmp(current->val, str) == 0) { current->cnt++; if (current->cnt == 2) { printf("%s\n", str); } flag = 1; break; } current = current->next; } if (!flag) { node *temp = new node; strcpy(temp->val, str); temp->next = nodeList[hight]->next; temp->cnt = 1; nodeList[hight]->next = temp; } } return 0; }