Monday, July 25, 2016

LeetCode [347] Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Note:
  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//quick sort: average complexity from O(n log n) to O(n), with a worst case of O(n2)
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int[][] pairs;
    
    void printPairs(){
        for(int[] p : pairs){
            System.out.print(p[0]+ ":" + p[1] + "  ");
        }
        System.out.println();
    }
    
    void swapPairs(int i, int j){
        int[] t = pairs[i];
        pairs[i] = pairs[j];
        pairs[j] = t;
    }
    
    public int[] topKFrequent(int[] nums, int k) {
        for(int i : nums){
            map.put(i, map.getOrDefault(i, 0)+1);
        }
        pairs = new int[map.size()][2];
        int i = 0;
        for(Map.Entry<Integer, Integer> e : map.entrySet()){
            pairs[i++] = new int[]{e.getKey(), e.getValue()};
        }
        selectPairs(0, map.size()-1, k);
        
        int[] ret = new int[k];
        for(int j=0; j<k; ++j){
            ret[j] = pairs[j][0];
        }
        return ret;
    }
    
    int partitionPairs(int l, int r){
 //       System.out.println("Before Sort");
 //       printPairs();
        int[] pivot = pairs[r];
        int i = l;
        for(int j=l; j<r; ++j){
            if(pairs[j][1]>=pivot[1]){
                swapPairs(i, j);
                i++;
            }
        }
        swapPairs(i, r);
        
 //       System.out.println("sort from " + l + "->" + i);
   //     printPairs();
        return i;
    }
    
    void selectPairs(int l, int r, int k){
        if(l>=r) return;
        int p = partitionPairs(l, r);
        if(p<k){
            selectPairs(p+1, r, k);
        }else{
            selectPairs(l, p-1, k);
        }
    }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
//minHeap: nlog(k)
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
        
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((a,b) -> Integer.compare(a.getValue(), b.getValue()));
        
        for(Map.Entry<Integer, Integer> e : map.entrySet()){
            minHeap.add(e);
            if(minHeap.size()>k) minHeap.poll();
        }
        
        int[] ret = new int[k];
        for(int i=0; i<k; ++i){
            ret[i] = minHeap.poll().getKey();
        }
        
        return ret;
    }
}


    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> freq = new HashMap<>();//value, freq
            int n = nums.length;
            List<Integer>[] buckets = new List[n+1];
            for(int i:nums){
                freq.put(i, freq.getOrDefault(i, 0)+1);
            }
            for(Map.Entry<Integer, Integer> e : freq.entrySet()){
                if(buckets[e.getValue()] == null){
                    buckets[e.getValue()] = new ArrayList<>();
                }
                buckets[e.getValue()].add(e.getKey());
            }

            List<Integer> ret = new ArrayList<>();
            for(int i=n; i>0; --i){
                if(buckets[i]!=null) ret.addAll(buckets[i]);
                if(ret.size()>=k) break;
            }

            return ret.subList(0, k).stream().mapToInt(i->i).toArray();
        }
    }
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)