第一问答网»论坛 › 中问网 › 问答 › 一道ACM题。用C++。求大神解答。

一道ACM题。用C++。求大神解答。

11 |

1 | 2013-3-13 09:05:21 | 显示全部楼层 |阅读模式

看了题目，想到了一个方法，具体代码就不写了。讲下思路。题目说到 M 和 N(1<=M<=4000,1<=N<=160000）,如果是双循环那么复杂度是M*N ,显然一秒不够。那么要快速判断数字是否存在，我想到了两种解决思路：一是hash，但没想到好的hash方案，c++的stl中的Map效率貌似又不怎么高，不想用。如果是用标记数组，可是数字的范围是0~2^31，内存不够。二就是字典树了，题目中讲到M远小于N，那么我们只要根据前M个数字去构建一颗字典树即可。后面N个数字依次在字典树中寻找即可，复杂度大概是 N*11 吧，1秒足够了，内存也耗费的不大。讲的思路中如果有什么不懂，可以谷哥或度娘，当然也可以追问。...

使用道具举报

返回列表发新帖

千问

主题	0 回帖	4882万积分

论坛元老

Rank: 8 Rank: 8

积分: 48824836

回复楼主返回列表

问答

热门排行