28ms JAVA solution


  • 2
    Y
    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
    
    		List<Integer> res = new ArrayList<Integer>();
    		
    		// count[i] indicates the number of integers that appear at least i times.
    		int[] count = new int[nums.length + 1];
    
    		HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
    		Integer t;
    		for (int num : nums) {
    			t = hashmap.get(num);
    			if (t == null) {
    				hashmap.put(num, 1);
    				count[1]++;
    			} else {
    				hashmap.replace(num, t + 1);
    				count[t+1]++;
    			}
    		}
            count[0] = count[1];
            
    		int minValue = 0; // the frequency of k-th frequent element
    		int dif = -1;
    
            // Binary Search: find minValue
    		int low = 0;
    		int high = count.length - 1;
    		while (low < high) {
    			int middle = (high + low) >> 1;
    			if (k == count[middle]) {
    				minValue = middle;
    				dif = 0;
    				break;
    			} else if (k < count[middle]) {
    				low = middle + 1;
    			} else {
    				high = middle - 1;
    			}
    		}
    		if (dif != 0) {
    			if (count[low] < k) {
    				minValue = low - 1;
    				dif = count[minValue] - k;
    			} else {
    				minValue = low;
    				dif = count[minValue] - k;
    			}
    		}
    
            // find the k most frequent elements
    		Iterator<Map.Entry<Integer, Integer>> iter = hashmap.entrySet().iterator();
    		if (dif == 0) {
    			while (iter.hasNext()) {
    				Map.Entry<Integer, Integer> entry = (Map.Entry<Integer, Integer>) iter
    						.next();
    				if ((int) entry.getValue() >= minValue) {
    					res.add((Integer) entry.getKey());
    				}
    			}
    		} else {
    			int v = 0;
    			while (iter.hasNext()) {
    				Map.Entry<Integer, Integer> entry = (Map.Entry<Integer, Integer>) iter
    						.next();
    				v = (int) entry.getValue();
    				if (v == minValue && dif > 0) {
    					res.add((Integer) entry.getKey());
    					dif--;
    				}
    				if (v > minValue) {
    					res.add((Integer) entry.getKey());
    				}
    			}
    		}
    		
    		return res;
        }
    }

Log in to reply
 

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