471. Top K Frequent words

Leave a comment

September 3, 2016 by oneOokay

amazon OA考的就是这个类似的题啊。思路就是:

  • 建一个Pair来存 key = string, 和word count
  • 一个HashMap<String, Integer>用来存word以及count
  • 再用一个Priority Q 把 Pair排序,最后poll入一个String[] 里。

这里注意的点大概是priority queue的comparator的order吧。

comparator : compare (x, y) :

  • if XXXX return 负数,则x在y前;
  • if XXXX return正数,则y在x前。

private class Pair{
String key;
int value;
public Pair(String k, int val){
key = k;
value = val;}}

private Comparator<Pair> comparator = new Comparator<Pair>(){
public int compare(Pair left, Pair right){
if (left.value != right.value) {//当word的出现次数不同的时候,比较word的出现次数
return left.value – right.value; //所有的leftValue – rightValue代表按value的从小到大排,value小的在priority queue前面。
}
return right.key.compareTo(left.key); //当word的出现次数相同时,按照word的alphabetical order 排。此时在priority queue中,字母表靠后的应该往前排(易于被poll出去).

//若right在left字母表之后,right.compareTo(left) > 0; left.compareTo(right) < 0; 这里对于priority queue需要把right放在left前面,则应该return 正数,所以应该写成right.compareTo(left).

//stringA.compareTo(stringB): The result is a positive integer if this String object lexicographically follows the argument string. The result is zero if the strings are equal; compareTo returns 0 exactly when the equals(Object) method would return true.
}
};

public String[] topKFrequentWords(String[] words, int k) {
if (k == 0) {
return new String[]{};
}
// Write your code here
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < words.length; i ++) {
if (map.containsKey(words[i])){
map.put(words[i], map.get(words[i]) + 1);
}else {
map.put(words[i], 1);
}
}

PriorityQueue<Pair> Q = new PriorityQueue<Pair>(k, comparator);
for (String word : map.keySet()){
Pair peek = Q.peek();
Pair newPair = new Pair(word, map.get(word));
if (Q.size() < k){
Q.add(newPair);
}else {
if (comparator.compare(newPair, peek) > 0) {
Q.poll();
Q.add(newPair);}}}

String[] result = new String[k];
for (int i = k – 1; i >= 0; i –) {
result[i] = Q.poll().key;
}
return result;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: