K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知单词总量不超过10万,允许极小概率的哈希冲突开销。
选择std::map<std::string, int>作为存储容器,因为其底层是红黑树,插入和查询的时间复杂度稳定为O(logn),性能比哈希容器更优。
选择std::unordered_set<std::string>作为存储容器,遍历所有单词插入集合后,遍历集合输出每个元素的count值即可得到出现次数。
若选择std::unordered_map<std::string, int>作为存储容器,必须手动为std::string类型实现自定义哈希函数,否则编译会报错。
选择std::unordered_map<std::string, int>作为存储容器,遍历每个单词执行counts[word]++即可完成统计,平均时间复杂度为O(n)(n为单词总数),符合性能要求。