Created
July 29, 2016 23:56
-
-
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/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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