Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created July 29, 2016 23:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/2482dbacb59e464d94c4a4d16cbc6d3b to your computer and use it in GitHub Desktop.
Save jianminchen/2482dbacb59e464d94c4a4d16cbc6d3b to your computer and use it in GitHub Desktop.
LC347 - K most frequent number - Java code - source code: http://www.guoting.org/leetcode/leetcode-347-top-k-frequent-elements/
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> frequencyMap=new HashMap<>();
for(int n:nums){
frequencyMap.put(n,frequencyMap.getOrDefault(n,0)+1);
}
Node[] heap=new Node[k];
int index=0;
for(Map.Entry<Integer,Integer> entry:frequencyMap.entrySet()){
int value=entry.getKey();
int times=entry.getValue();
Node node=new Node(value,times);
if(index!=k){
heap[index]=node;
heapInsert(heap,index++);
}else{
if(heap[0].times<node.times){
heap[0]=node;
heapify(heap,0,k);
}
}
}
for(int i=index-1;i!=0;i--){
swap(heap,0,i);
heapify(heap,0,i);
}
List<Integer> result=new ArrayList();
for(int i=0;i!=heap.length;i++){
result.add(heap[i].value);
}
return result;
}
public void heapInsert(Node[] heap,int index){
while(index!=0){
int parent=(index-1)/2;
if(heap[index].times<heap[parent].times){
swap(heap,parent,index);
index=parent;
}else{
break;
}
}
}
public void heapify(Node[] heap,int index,int heapSize){
int left=index*2+1;
int right=index*2+2;
int smallest=index;
while(left<heapSize){
if(heap[left].times<heap[index].times){
smallest=left;
}
if(right<heapSize&&heap[right].times<heap[smallest].times){
smallest=right;
}
if(smallest!=index){
swap(heap,smallest,index);
}else{
break;
}
index=smallest;
left=index*2+1;
right=index*2+2;
}
}
public void swap(Node[] heap,int index1,int index2){
Node tmp=heap[index1];
heap[index1]=heap[index2];
heap[index2]=tmp;
}
public class Node{
public int value;
public int times;
public Node(int value,int times){
this.value=value;
this.times=times;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment