Average O(n) based on quickselect


  • 0
    N
    public class Solution {
        public static class Element {
    			int freq;
    			int val;
    			public Element(int val, int freq) {
    				this.val = val;
    				this.freq = freq;
    			}
    	}
        public List<Integer> topKFrequent(int[] nums, int k) {
            Element[] elements = initElementArray(nums);
    		int end = quickselect(elements,0,elements.length - 1, k);
    		List<Integer> res = new ArrayList<>();
    		for(int i = 0; i <= end; i++) {
    		    res.add(elements[i].val);
    		}
    		return res;
        }
    	private Element[] initElementArray(int[] nums) {
    		Map<Integer,Integer> countMap = new HashMap<>();
    		for(int num : nums) {
    			Integer count = countMap.get(num);
    			if (count == null) {
    				countMap.put(num,1);
    			} else {
    				countMap.put(num, count + 1);
    			}
    		}
    		Element[] es = new Element[countMap.size()];
    		int i = 0;
    		for(Map.Entry<Integer,Integer> entry : countMap.entrySet()) {
    			int val = entry.getKey(), freq = entry.getValue();
    			es[i++] = new Element(val,freq);
    		}
    		return es;
    	}
    	
    	private void swap(Element[] es, int i, int j) {
    		Element tmp = es[i];
    		es[i] = es[j];
    		es[j] = tmp;
    	}
    	private int quickselect(Element[] elements, int left, int right, int k) {
    	    if (left > right) {
    	        return -1;
    	    }
    		int pivot = elements[right].freq;
    		int i = left, j = right - 1;
    		//xxxxxPxxxxxx
    		while(i <= j) {
    			if(elements[i].freq > pivot) {
    				i++;
    			} else {
    				swap(elements,i,j--);
    			}
    		}
    		swap(elements,i,right);
    		int larger = i - left + 1;
    		if(larger == k) {
    		    return i;
    		}
    		if(larger > k) {
    			right = i - 1;
    		} else {
    			left = i + 1;
    			k = k - larger;
    		}
    		return quickselect(elements,left,right,k);
    	}
    }

Log in to reply
 

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