H**********5
发帖数: 2012 | 1 满足了O(n)，用的trie+minHeap。
看了下行数180行。
着他妈要是事前没准备没背题的话，onsite让你实现个O(n)，有多少人能写出来？不是
讲大致思路啊，是一行一行全部实现，建tri,建insert函数，tri节点插入minHeap函数。
结论:以后的刷题有可能进化成背题背最优解了，就看谁能花时间花精力准备 |
D**********0
发帖数: 1022 | |
z*******o
发帖数: 4773 | 3 这题你用tie把面试官惊艳了
啪一拍椅子, "I want you!" |
H**********5
发帖数: 2012 | 4 问题是不用trie如何达到O(n)?
: 这题你用tie把面试官惊艳了
: 啪一拍椅子, "I want you!"
【在 z*******o 的大作中提到】
: 这题你用tie把面试官惊艳了
: 啪一拍椅子, "I want you!"
|
z*******o
发帖数: 4773 | 5 你把log(k)吞了?
【在 H**********5 的大作中提到】
: 问题是不用trie如何达到O(n)?
:
:
: 这题你用tie把面试官惊艳了
:
: 啪一拍椅子, "I want you!"
:
|
H**********5
发帖数: 2012 | 6 trie minheap加一起，可以达到O(n)吧，不是O(n)*lgk。上午偷闲写的代码，自己生成
的大文件在eclipse里跑了下ok，不想贴代码。
: 你把log(k)吞了?
【在 z*******o 的大作中提到】
: 你把log(k)吞了?
|
D**********0
发帖数: 1022 | 7 我写的：
class Solution {
public List topKFrequentWords(String[] words, int k) {
Map map = new HashMap<>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
PriorityQueue> pq = new PriorityQueue<>(
(n1, n2) -> n2.getValue() - n1.getValue());
for (Map.Entry entry : map.entrySet()) {
pq.offer(entry);
}
List res = new ArrayList<>();
for (int i = 0; i < k; i++) {
res.add(pq.poll().getKey());
}
return res;
}
} |
H**********5
发帖数: 2012 | 8 这个是O(n)*lgk，面试官假如要O(n)?
: class Solution {
: public List topKFrequentWords(String[] words, int k) {
: Map map = new HashMap();
: for (String word : words) {
: map.put(word, map.getOrDefault(word, 0) 1);
: }
:
: PriorityQueue pq = new PriorityQueue(
: (n1, n2) -
【在 D**********0 的大作中提到】
: 我写的：
: class Solution {
: public List topKFrequentWords(String[] words, int k) {
: Map map = new HashMap<>();
: for (String word : words) {
: map.put(word, map.getOrDefault(word, 0) + 1);
: }
:
: PriorityQueue> pq = new PriorityQueue<>(
: (n1, n2) -> n2.getValue() - n1.getValue());
|
D**********0
发帖数: 1022 | 9 那就桶排序吧。
不然每个单词入树的时候复杂度是多少？
【在 H**********5 的大作中提到】
: 这个是O(n)*lgk，面试官假如要O(n)?
:
:
: class Solution {
:
: public List topKFrequentWords(String[] words, int k) {
:
: Map map = new HashMap();
:
: for (String word : words) {
:
: map.put(word, map.getOrDefault(word, 0) 1);
:
: }
:
:
:
: PriorityQueue pq = new PriorityQueue(
|
H**********5
发帖数: 2012 | 10 桶排序也到不了O(n)。
翻了下geeks for geeks，有个烙印用C加加实现的。每次把点同时插到trie和minHeap
，我用java重新写了一遍。
: 那就桶排序吧。
: 不然每个单词入树的时候复杂度是多少？
【在 D**********0 的大作中提到】
: 那就桶排序吧。
: 不然每个单词入树的时候复杂度是多少？
|
k**********i
发帖数: 36 | 11 什么鬼.
O(n)的算法是 hash + Quick Selection |
u********s
发帖数: 1047 | |
e***u
发帖数: 384 | 13 才发现这个是正解。
【在 k**********i 的大作中提到】
: 什么鬼.
: O(n)的算法是 hash + Quick Selection
|
