清华OJ：PA3-3 重名剔除(Deduplicate)难题精解

题目：https://dsa.cs.tsinghua.edu.cn/oj/problem.shtml?id=1150html

分析：数组

题目涉及字符串，提示用散列。不难想到散列码转换，根据邓公教材上的方法，字符串的散列码取做，其中常数a>=2，但若用这一方法，获得的值会超出int范围上限，不值得。故将上式改成，这样远远不会达到int范围上限。至于散列函数的设计，通常用除余法便可，故可在获得散列码后，直接除余，余数即散列表长，通常选用不小于输入规模上限的素数便可，此题是600001。转换后的散列码可能重复，等效于不一样关键码（字符串）映射到同一地址，故须要解决冲突。函数

解决冲突的方法不少，经常使用的是开放定址法的线性探测法，可是这一方法会致使超时，缘由在于当出现冲突时，最坏状况下须要遍历以前全部的非空桶单元，所以此法不妥。此题通常适用的方法是独立链法，即将冲突的关键码组织成列表放在映射到的桶单元中，发生冲突时，最坏状况下只需遍历当前桶单元的全部冲突关键码，相较于前一方法，时间成本获得了极大下降。测试

除了上述方法正确以外，还须要结合题目，此题要求重复的字符串只输出1次，故须要增设额外标志，通常是在桶单元的每一个槽位（冲突单元）中设置，能够设为布尔型，初始化为假，若当前输入的字符串与映射到的字符串重复，且当前对应的槽位标志为假，则将其改成真，输出这个字符串，这样以后重复的字符串不会被输出。spa

有了正确的基本方法和结合题目的特殊方法，通常能够经过。至于每一个槽位中的数据域的选取，通常选取字符串，而为了赋值方便，通常使用C++的string类型，可是这样作经过后，会发现最坏用例耗时1200+ms。不难发现，其缘由在于每次字符串的赋值致使时间成本的迅速升高。因而，将数据域取字符指针，因而数据域的每次赋值只需O(1)的时间。经测试，此方法最坏用例仅耗时200+ms，相较于前一方法，效率提高了近5倍！设计

若槽位数据域选用字符指针，则须要注意，你须要在主函数以外定义一个二维字符数组，缘由有两点，一是字符（串）指针须要取一个字符二维数组的第1维，这样就指向了一个字符串，而这个字符串的首字符地址是惟一的，这样能够保证每一个槽位字符指针不至于重复。二是数组若在主函数以内定义，运行会出错。最后注意数组第2维度长度即字符串最大长度，需至少为41，缘由是字符串须要有结束符。指针

掌握基本方法，利用好题目条件，注意和处理好和题目相关的全部细节，定能AC!code

代码：htm

#include<cstdio>
#include<cstring>
#define HASHSIZE 600001
using namespace std;
struct Slot {//每一个桶对应的槽位，存储冲突，即映射到同一地址且不重复的字符串（实则字符指针） 
	char* data;//数据项，存储字符指针 
	bool repeat;//标志，判别字符串是否重复
	Slot* succ;//后继 
}buckets[HASHSIZE];//桶数组（散列表） 
char name[HASHSIZE][41];//字符二维数组（必须开头定义），存储输入字符串，注意二维长度为40+1个结束符=41 
void Insert(int addr, char* s) {//在相应地址中插入冲突的字符串（实则字符指针） 
	Slot* t = new Slot;
	t->data = s; t->repeat = false;//初始化当前字符串从未重复 
	t->succ = buckets[addr].succ;//链表头插法 
	buckets[addr].succ = t;
}
int HashCode(char* s) {//散列码转换（字符串转数字） 
	int sum = 0, len = strlen(s);
	for (int i = 0; i<len; i++)//多项式求和 
		sum += (i + 1)*(s[i] - 'a'+1);
	return sum;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){		
		scanf("%s", name[i]);
		int addr = HashCode(name[i]) % HASHSIZE;//得到映射到的地址 
		Slot* p = buckets[addr].succ;//从当前桶的第1个槽位开始 
		while (p)//遍历全部槽位（冲突的单元） 
		if (!strcmp(p->data, name[i])) {//若当前槽位的字符串重复 
			if (!p->repeat) {//检查当前槽位的字符串是否重复
				p->repeat = true;//若未重复，则标志为已重复过 
				puts(name[i]);//输出重复字符串 
			}break;//若重复过，则忽略，不管是否重复过，皆终止遍历 
		}
		else p = p->succ;
		if (!p)Insert(addr, name[i]);//若当前槽位空，则进行插入 
	}
	return 0;
}