Own implementation of MaxHeap(good for beginners). O(n) space complexity and O(n*logn) worst time complexity. Java


  • -1
    O
    public class Solution {
        public static List<Integer> topKFrequent(int[] nums, int k) {
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            for(int val: nums) {
            	if (map.containsKey(val)) {
            		map.put(val, map.get(val)+1);
            	} else {
            		map.put(val, 1);
            	}
            }
            int[] heap = buildHeap(map);
    		int temp, size = heap.length-1;
    		for(int i = 0; i < heap.length; i++) {
    			temp = heap[0];
    			heap[0] = heap[size];
    			heap[size] = temp;
    			size--;
    			percolateDown(heap, 0, size, map);
    		}
            List<Integer> result = new ArrayList<Integer>();
            for(int i = heap.length-1, j = 0; i >= 0 && j < k; i--, j++) {
            	result.add(heap[i]);
            }
            
            return result;
        }
        
        public static int[] buildHeap(HashMap<Integer, Integer> map) {
            int[] result = new int[map.size()];
            int i = 0;
            for(int key: map.keySet()) {
            	result[i++] = key;  
            }
            for(i = (result.length - 1)/2; i >= 0; i--) {
            	percolateDown(result, i, result.length-1, map);
            }
            
            return result;
        }
        
        public static void percolateDown(int[] items, int i, int size, HashMap<Integer, Integer> map) {
        	if (i > size || i < 0) {
    			return ;
    		}
    		int max = i, temp = -1, left, right;
    		left  = 2*i+1;
    		right = 2*i+2;
    		if (left <= size && map.get(items[left]) > map.get(items[i])) {
    			max = left;
    		} 
    		if (right <= size && map.get(items[right]) > map.get(items[max])) {
    			max = right;
    		}
    		if (max != i) {
    			temp       = items[i];
    			items[i]   = items[max];
    			items[max] = temp;
    			percolateDown(items, max, size, map);
    		}
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.