数字流的秩、单词频率（哈希实现）

题目1：数字流的秩

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

实现 track(int x) 方法，每读入一个数字都会调用该方法；

实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

示例：

输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]

解题思路：

1.创建哈希表，将数字x的出现的次数保存起来

2.遍历map，找到小于或等于x的key值，将其value值进行累加，得到最终答案。

Code：

 

class StreamRank {
public:unordered_map<int,int> map;//创建哈希表//map[x]存放的是数字x出现的次数StreamRank() {}void track(int x) {//如果当前数字第一次出现，则map[x]=1if(map.find(x)==map.end()){map[x]=1;}//不是第一次出现，就添加到相应的map[x]中else{map[x]+=1;}}int getRankOfNumber(int x) {int count=0;//小于或等于 x 的值的个数//遍历mapfor(auto it=map.begin();it!=map.end();it++){//只要key值小于或等于x，就将value值累加if(it->first<=x){count+=it->second;}}//返回总个数return count;}
};

题目2：单词频率

设计一个方法，找出任意指定单词在一本书中的出现频率。

你的实现应该支持如下操作：

• WordsFrequency(book)构造函数，参数为字符串数组构成的一本书

• get(word)查询指定单词在书中出现的频率

示例：

WordsFrequency wordsFrequency = new WordsFrequency({"i", "have", "an", "apple", "he", "have", "a", "pen"});
wordsFrequency.get("you"); //返回0，"you"没有出现过
wordsFrequency.get("have"); //返回2，"have"出现2次
wordsFrequency.get("an"); //返回1
wordsFrequency.get("apple"); //返回1
wordsFrequency.get("pen"); //返回1

解题思路：

本题与上一题大体上是一致的。

1.创建哈希表，将单词出现的次数保存起来

2.直接返回该单词的出现频率map[word]

Code：

class WordsFrequency {
public:unordered_map<string,int> map;WordsFrequency(vector<string>& book) {//保存每个单词的出现次数for(string& str:book){map[str]+=1;}}int get(string word) {//返回该单词的出现频率map[word]return map[word];}
};