首页 > 试题广场 > 词频统计
[编程题]词频统计
  • 热度指数:6810 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个string数组article及其大小n及一个待统计单词word,请返回该单词在数组中出现的频数。文章的词数在1000以内。

C++也可以用hashtable的呀~~

#include <unordered_map>

class Frequency {
public:
    int getFrequency(vector<string> article, int n, string word) {
        unordered_map<string, int> hashtable;
        for (int i = 0; i < n; i++) {
            hashtable[article[i]]++;
        }
        
        return hashtable[word];
    }
};

编辑于 2016-06-21 22:17:19 回复(0)

python solution

return article.count(word)
发表于 2017-10-01 22:53:22 回复(2)
题目情景确实不好
import java.util.*;

public class Frequency {
    public int getFrequency(String[] article, int n, String word) {
        // write code here
        int count=0;
        for(int i=0;i<article.length;i++){
            if(article[i].compareTo(word)==0) count++;
        }
        return count;
    }
}
发表于 2017-06-15 10:43:47 回复(0)
注意:这个方法只适用于字符串,不适用于结构体这种对象,同时,这种方法也比较消耗内存,当然,字符串上的效率是极高的,比map、手写红黑树等好多了,还容易实现。
当然,查询次数只有一次,让这个方法看着太呆萌了——复杂度是O(n*length+length),在这种情况下和暴力没什么区别。但是如果是查询q次,这种方法的复杂度是O(n*length+q*length),比暴力的O(n*q*length)好多了。

这里选用的数据结构,叫字典树(Trie)。
在这里并不想画多少时间介绍这个数据结构,因为这个数据结构还是很简单和直观的(相比二叉平衡树,容易太多了)。插入和查找的时间复杂度只取决于你的当前单词的长度O(length)。
但是Trie比较消耗内存,怎么办?
搜索引擎实现的时候,一种变通方法是,借用二叉搜索树的思路实现一个三叉Trie——其中查询串中当前字符比指向的节点字符小的时候,去左儿子,大的时候去右儿子,相等的时候则向下走一层。

统计一个单词出现的次数?这个在Trie上很简单。插入的时候,每个节点新增一个count域,记录以这个节点为结尾的单词数有几个,就好了。

代码如下:

struct Node{
    char data;
    int cnt;
    int ch[2],next;// 0 left child, 1 right child
    Node(){}
    Node(char c):data(c){cnt=ch[0]=ch[1]=next=0;}
};

struct Trie{
    Node* node;
    int nodecount;
	
    Trie(){
        node=new Node[500005];
        node[0]=Node('n');
        nodecount=1;
    }
    ~Trie(){
        delete [] node;
    }
    
    int appendnode(char x){
        node[nodecount]=Node(x);
        return nodecount++;
    }

    void append(int id,const char* str){
        while(*str){
            if(*str==node[id].data){
                if(!str[1])node[id].cnt++;
                if(!node[id].next&&str[1]){
                    node[id].next=appendnode(str[1]);
                }
                id=node[id].next;
                str++;
            }else{
                int cid=*str<node[id].data?0:1;//0 left child, 1 right child
                if(!node[id].ch[cid]){
                    node[id].ch[cid]=appendnode(str[0]);
                }
                id=node[id].ch[cid];
            }
        }
    }

    int find(int id,const char *str){
        while(*str){
            if(*str==node[id].data){
                if(!str[1])return id;
                if(!node[id].next){
                    return -1;
                }
                id=node[id].next;
                str++;
            }else{
                int cid=*str<node[id].data?0:1;//0 left child, 1 right child
                if(!node[id].ch[cid]){
                    return -1;
                }
                id=node[id].ch[cid];
            }
        }
        return -1;
    }
};

class Frequency {
public:
    int getFrequency(vector<string> article, int n, string word) {
        Trie trie;
        for(int i=0;i<n;i++){
            trie.append(0,article[i].c_str());
        }
        int id=trie.find(0,word.c_str());
        return trie.node[id].cnt;
    }
};

发表于 2015-08-15 18:14:24 回复(6)
//看了一遍,有位大神使用trie树实现的,但是是用c++,我就给一个java实现的吧,思路就是那位c++大神的
import java.util.*;

class TrieNode {
    private TrieNode[] children;
    public boolean isWord;
    public int cnt;
    
    public TrieNode() {
        children = new TrieNode[26];
        isWord = false;
        cnt = 0;
    }
    
    public void insert(String word, int index) {
        if (index == word.length()) {
            isWord = true;
            ++cnt;
            return;
        }
        
        int c = word.charAt(index) - 'a';
        if (children[c] == null) {
            children[c] = new TrieNode();
        }
        
        children[c].insert(word, index + 1);
    }
    
    public TrieNode search(String word, int index) {
        if (index == word.length()) {
            return this;
        }
        
        int c = word.charAt(index) - 'a';
        if (children[c] == null) {
            return null;
        }
        
        return children[c].search(word, index + 1);
    }
}

public class Frequency {
    public int getFrequency(String[] article, int n, String word) {
        // write code here
        TrieNode root = new TrieNode();
        for (String str : article) {
            root.insert(str, 0);
        }
        
        if (word == null || word.length() == 0) {
            return 0;
        }
        
        TrieNode ans = root.search(word, 0);
        if (ans != null && ans.isWord == true) {
            return ans.cnt;
        } 
        
        return 0;
    }
}
编辑于 2017-08-21 13:50:41 回复(3)
import java.util.*;

public class Frequency {
    public int getFrequency(String[] article, int n, String word) {
        // write code here
        short num = 0;
        for(short i=0;i<n;i++) {
            if(word.equals(article[i])) num++;
        }
        return num;
    }
}
最容易想到的顺序遍历,献丑了
运行时间:32ms
占用内存:10172K
发表于 2019-07-26 14:55:56 回复(1)

C++ 一句话:

return count(article.begin(), article.end(), word);
发表于 2018-05-29 19:21:06 回复(0)
import java.util.*;
public class Frequency {
    public int getFrequency(String[] article, int n, String word) {
        // write code here
        HashMap<String,Integer> map=new HashMap<String,Integer>();
        for(int i=0;i<article.length;i++){
            if(!map.containsKey(article[i])){
                map.put(article[i],1);
            }
            else{
                int tem=map.get(article[i]);
                tem++;
                map.put(article[i],tem);
            }
        }
        if(!map.containsKey(word))
            return 0;
        return map.get(word);
    }
}
 
发表于 2019-05-26 16:31:41 回复(0)
Python开挂

# -*- coding:utf-8 -*-

class Frequency:
    def getFrequency(self, article, n, word):
        return article.count(word)

发表于 2018-12-26 16:12:01 回复(0)
import java.util.*;
/*
思路:感觉有好多种方法做这道题目,我就选择其中最传统的把,就是顺序遍历过去
*/
public class Frequency {
    public int getFrequency(String[] article, int n, String word) {
        int count=0;
        for(int i=0;i<n;i++){
			if(article[i].equals(word)) count++;
        }
        return count;
    }
}
运行时间:82ms
占用内存:10368k

发表于 2017-07-06 12:44:49 回复(0)
class Frequency {
public:
    int getFrequency(vector<string> article, int n, string word) {
        return count(article.begin(), article.end(), word);
    }
};

编辑于 2016-08-27 16:38:05 回复(1)
题目好容易想复杂,数组中每个元素都是一个string, 但是只包含一个单词,直接逐一比较即可,是则加1。 还以为每个元素都是一个句子,想到要用KMP算法去了
发表于 2016-08-24 18:53:18 回复(0)
/**
*看到你们写得好复杂,可能是算法工程师该有的品质和本能,c语言和c++学得并不算好,
*所以比较中情java,闲话少说,我来分享一下我自己的算法,我是每一次都拿那个word去
*和那篇文章的每一个字符串比,如果相等的话,就count+1,判断结束,返回count
**/

public class Frequency {
    public int getFrequency(String[] article, int n, String word) {
        // write code here
        int count=0;
        for(int i=0;i<article.length;i++){
            if(article[i].equals(word)){
                count++;
            }
        }
        return count;
    }
}
发表于 2016-04-12 14:01:09 回复(0)
不知道大神们为什么写的那么复杂,红黑树字典树什么的我不太熟练,但是我这个也通过了
思想是这样的,为了节省时间,首先比较目标词和文章中的词汇长度是否相同,若相同,再进一步比较是否是同一个词,从string数组第一个跑一边,就可以检查出来了,因为比较是逐个字母比较,所以长度不同直接排除,可以节省不少时间。
class Frequency {
public:
    int getFrequency(vector<string> article, int n, string word) {
        // write code here
        int i=0,num=0;
        while(i<n)
        {
        if(article[i].length()==word.length())
            if(article[i]==word)
                num++
            i++;
        }
        return num;
    }
};
发表于 2017-01-20 15:24:22 回复(0)
题出的有问题,没有告诉使用场景。  牛客的工程师还是没有那么大的精力啊。。。
发表于 2016-08-25 11:40:10 回复(0)
import java.util.*;

public class Frequency {
    public int getFrequency(String[] article, int n, String word) {
        // write code here
        int c = 0;
        for(int i=0;i<n;i++){
            if(article[i].equals(word)){
                c++;
            }
        }
        return c;
    }
}

发表于 2020-10-22 08:42:25 回复(0)
把题目想麻烦了,导致还用了一个map存数据
class Frequency {
public:
    int getFrequency(vector<string> article, int n, string word) {
        // write code here
        map<string,int> mm;
        for(int i=0;i<article.size();++i){
            auto iter=mm.find(article[i]);
            if(iter!=mm.end()){
                iter->second++;
            }else{
                mm.insert(pair<string, int>(article[i],1));
            }
        }
        auto iter=mm.find(word);
        if(iter!=mm.end()){
            return iter->second;
        }else{
            return 0;
        }
    }
};

发表于 2020-09-03 23:59:41 回复(0)
跟着大神用trie树实现,添加一个python版本的
class TrieNode(object):
    def __init__(self,value=None,count=0,parent = None):
        self.value = value
        self.count = count
        self.parent = parent
        self.children = {}

class Trie(object):
    def __init__(self):
        self.root = TrieNode()
    def insert(self,sequence):
        cur_node = self.root
        for item in sequence:
            if item not in cur_node.children:
                child = TrieNode(value=item,count=0,parent=cur_node)
                cur_node.children[item] = child
                cur_node = child
            else:
                cur_node = cur_node.children[item]
                #cur_node.count+=1
        cur_node.count+=1
    def search(self,sequence):
        cur_node = self.root
        mark = True
        for item in sequence:
            if item not in cur_node.children:
                mark = False
                break
            else:
                cur_node = cur_node.children[item]
        if mark==0:
            return 0
        else:
            return cur_node.count
    
class Frequency:
    def getFrequency(self, article, n, word):
        trie = Trie()
        for i in range(n):
            trie.insert(article[i])
        return trie.search(word)


发表于 2020-08-10 15:45:47 回复(0)
class Frequency {
public:
    int getFrequency(vector<string> article, int n, string word) {
        n = 0;
        for(auto& s : article) {
            if(s==word)
                n++;
        }
        return n;
    }
};

发表于 2020-07-20 22:42:55 回复(0)
import java.util.*;
class TrieNode {
     public char val;
     public boolean isWord;
     public int cnt;
     public TrieNode[] children = new TrieNode[26];
     public TrieNode() {}
     TrieNode(char c){
         this.val = c;
     }   
 } 

 class Trie {
    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode(' ');
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode ws = root;
        for(int i=0 ; i < word.length() ; i++){
            char c = word.charAt(i);
            if(ws.children[c- 'a'] == null){
                ws.children[c - 'a'] = new TrieNode(c);
            }
            ws = ws.children[c - 'a'];
        }
        ws.isWord = true;
        ws.cnt++;
    }
    
    /** Returns if the word is in the trie. */
    public int search(String word) {
        TrieNode ws = root;
        ws = helper(word,0,ws);
        return (ws != null && ws.isWord) ? ws.cnt : 0;
    }

    private TrieNode helper(String word,int start,TrieNode pointer){
        if(word.length() == start) return pointer;
        char c = word.charAt(start);
        if(pointer.children[c - 'a'] == null) return null;
        return helper(word,start+1,pointer.children[c - 'a']);
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode ws = root;
        ws = helper(prefix,0,ws);
        return ws == null ? false : true;
    }
}

public class Frequency {
    public int getFrequency(String[] article, int n, String word) {
        // write code here
        Trie trie = new Trie();
        for(String s : article){
            trie.insert(s);
        }
        return trie.search(word);
    }
}
单词树的解法,测试用例应该没有大写字母了,这么写就过了。
发表于 2019-12-22 17:18:39 回复(0)