百度之星程序设计大赛
higer
#include <stdio.h>
int main(){
return 0;
}
孔令军
zhong nanhai
On 5/30/09, 孔令军 <allenk...@gmail.com> wrote:
> what？
>
>
> 2009-05-30
>
>
>
> 孔令军
孔令军
yuziyu
孔令军 写道:
> 象搜索的输入信息是一个字符串，统计 300万输入信息中的最热门的前十条，我
> 们每次输入的一个字符串为不超过255byte,内存使用只有1G,
> 请描述思想，写出算发（c语言），空间和时间复杂度。
>
孔令军
yuziyu
struct hash_node{
string str;
int cnt;
};
void solve()
{
vector< list<hash_node> > hash_table( MAX_HASH_VALUE );
string str;
while ( cin>>str){
int hash_value = compute_hash(str);
//在hash_table[hash_value]这个链表中查找str,如果找到，计数加1。没有，插
入链表中.
}
//遍历hash表，扫描10次选出最大的10个..或者用个小顶堆
}
字符串hash算法有很多种。。
这有个链接
http://blog.csdn.net/tarmee/archive/2007/08/16/1746442.aspx
>
yuziyu
孔令军 写道:
> 鱼头 详细说一下 怎样hash？
>
>
孔令军
yuziyu
我随便说的
孔令军 写道:
> 谢谢哈这需要在内存中存放一张hash表吧 内存一定能存下？
> 2009-06-16
> ------------------------------------------------------------------------
> 孔令军
> ------------------------------------------------------------------------
> *发件人：* yuziyu
> *发送时间：* 2009-06-16 22:37:51
> *收件人：* bianchengai...@googlegroups.com
> *抄送：*
> *主题：* Re:一道题
> struct hash_node{
> string str;
> int cnt;
> };
> void solve()
> {
> vector< list<hash_node> > hash_table( MAX_HASH_VALUE );
> string str;
> while ( cin>>str){
> int hash_value = compute_hash(str);
> //在hash_table[hash_value]这个链表中查找 str,如果找到，计数加1。没有，插
yuziyu
255个字节，trie树的高度最大为255,空间复杂度为26*255。
时间复杂度为O(n).
孔令军 写道:
> 谢谢哈这需要在内存中存放一张hash表吧 内存一定能存下？
> 2009-06-16
>
> -~----------~----~----~----~------~----~------~--~---
>
yuziyu
用trie实现了一下，没严格测试。g++ 下简单数据测试通过。
主要思路就是先用trie树存储所有的字符串。然后遍历trie树，用小顶堆存储
top10的字符串。
时间复杂度为O(n) 不过常数因子应该会比较大。
空间复杂度为(255*256).应为常数。
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <queue.h>
struct trie_node{
bool is_terminal;
int cnt;
trie_node *sons[256];
trie_node(){
is_terminal = false;
cnt = 0;
memset(sons,0,sizeof(sons));
}
};
int insert_str(trie_node *root,char *str)
{
int i = 0;
trie_node * cur = root;
while( str[i]!='\0' ){
if(cur->sons[(int)str[i]]==NULL){
cur->sons[(int)str[i]] = new trie_node;
}
if( str[i+1]=='\0' ){
//最后一个字符
cur->sons[(int)str[i]]->is_terminal = true;
cur->sons[(int)str[i]]->cnt++;
return cur->sons[(int)str[i]]->cnt;
}else{
cur = cur->sons[(int)str[i]];
++i;
}
}
return 0;
}
struct heap_node{
char *str;
int cnt;
};
char *result[10];
int top10[10];
char str_buf[255];
priority_queue< heap_node > heap;
bool operator<(const heap_node&h1,const heap_node&h2)
{
return h1.cnt>h2.cnt;
}
void _traverse(trie_node *root, int depth)
{
static int arrived = 0;
arrived++;
if(root->is_terminal){
//是终端结点
if(arrived<=10){
char *temp = (char*)malloc(depth+1);
str_buf[depth]='\0';
memcpy(temp,str_buf,depth+1);
heap_node node;
node.cnt = root->cnt;
node.str = temp;
heap.push(node);
}else{
heap_node node = heap.top();
if(root->cnt>node.cnt){
heap.pop();
free(node.str);
char *temp = (char*)malloc(depth+1);
str_buf[depth]='\0';
memcpy(temp,str_buf,depth+1);
node.cnt = root->cnt;
node.str = temp;
heap.push(node);
}
}
}
for(int i=0;i<256;++i){
if( root->sons[i] != NULL ){
str_buf[depth] = i;
_traverse(root->sons[i],depth+1);
}
}
}
void traverse(trie_node*root)
{
_traverse(root,0);
}
void solve()
{
trie_node root;
char buf[256];
while( fgets(buf,256,stdin)){
buf[strlen(buf)-1]=0;//去掉换行符...
insert_str(&root,buf);
}
traverse(&root);
while( !heap.empty() ){
//由于是小顶堆，从第10名到第1名输出.
heap_node node = heap.top();
printf("string:%s,count:%d\n",node.str,node.cnt);
heap.pop();
free(node.str);
}
}
int main()
{
solve();
return 0;
}
孔令军 写道:
> 谢谢哈这需要在内存中存放一张hash表吧 内存一定能存下？
>
>
> -~----------~----~----~----~------~----~------~--~---
>
nobody
我犯傻了．．．空间复杂度也是O(n).
hash和trie的做法时间和空间都是O(n).不过hash的空间要比trie的空间大，时间要比tire小．
255*3 000 000 <1G...
理论上用hash和trie都行．．不过可能用trie更好一些
孔令军
Ziyu Yu
孔令军 写道: