POJ2503两种解法:快速排序+2分查找与哈希表
POJ2503两种解法:快速排序+二分查找与哈希表
poj2503题目意思很简单:就像查找一本字典,根据输入的条目和要查询的单词,给出查询结果(每个单词长度不超过10)。这题有很多实现方式,最容易想到的就是map,但这是acm训练且stl里面的map速度不够快,那就要另谋出路。
数据量为100,000。可以想到的是快排+二分,复杂度是O(nlog2n)。还有就是哈希,哈希查询时间是O(1),当然,还要考虑哈希冲突,设计合理的字符串哈希函数。
首先是快排+二分,比较简单。
#include <iostream> const int MAX = 100001; typedef struct { char e[11]; char f[11]; }Entry; Entry entry[MAX]; int i = 0; //词典总条数 int cmp(const void *a, const void *b) { return strcmp((*(Entry *)a).f, (*(Entry *)b).f); } int BinSearch(char c[]) { int low = 0, high = i - 1; int mid, t; while(low <= high) { mid = (low + high) / 2; t = strcmp(entry[mid].f, c); if(t == 0) return mid; else if(t == -1) low = mid + 1; else high = mid - 1; } return -1; } int main() { char str[25]; int index = -1; while(gets(str)) { if(str[0] == '\0') break; sscanf(str,"%s%s",entry[i].e,entry[i].f); i++; } qsort(entry,i,sizeof(Entry),cmp); while(gets(str)) { index = BinSearch(str); if(index == -1) printf("eh\n"); else printf("%s\n",entry[index].e); } return 0; }
对于字符串的哈希,在《算法艺术与信息学竞赛》推荐使用ELFHash函数。对于哈希冲突的处理,采用的是链表法(个人认为线性探测等效率不是很高)。
#include <iostream> const int M = 149993; typedef struct { char e[11]; char f[11]; int next; }Entry; Entry entry[M]; int i = 1; //词典总条数 int hashIndex[M]; int ELFHash(char *key) { unsigned long h=0; while(*key) { h=(h<<4)+(*key++); unsigned long g=h&0Xf0000000L; if(g) h^=g>>24; h&=~g; } return h%M; } void find(char f[]) { int hash = ELFHash(f); for(int k = hashIndex[hash]; k; k = entry[k].next) { if(strcmp(f, entry[k].f) == 0) { printf("%s\n",entry[k].e); return; } } printf("eh\n"); } int main() { char str[22]; while(gets(str)) { if(str[0] == '\0') break; sscanf(str,"%s %s",entry[i].e,entry[i].f); int hash = ELFHash(entry[i].f); entry[i].next = hashIndex[hash]; hashIndex[hash] = i; i++; } while(gets(str)) find(str); return 0; }