小编use*_*187的帖子

我想取一个int作为输入,并返回第k位.

int getBit(int n, int k){
    return kth bit in n;
}

我该怎么办？

假设您有一个巨大的文件,比如1GB.该文件在每行包含一个单词(总共n个单词),并且您希望在文件中找到k个最常用的术语.

现在,假设您有足够的内存来存储这些单词,那么在减少内存使用和Big-O复杂性的持续开销方面,有什么更好的方法来解决问题？我相信可以使用两种基本算法:

1. 使用哈希表和最小堆来存储事件和看到的前K个单词.这是O(n + nlogk)~O(N)
2. 使用trie存储单词和出现次数,然后遍历trie以计算最常用的单词.这是O(n*p)~O(N),其中p是最长字的长度.

哪种方法更好？

另外:如果你没有足够的内存用于哈希表/ trie(即10MB左右的有限内存),那么最好的方法是什么？