347. Top K Frequent Elements

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example, Given [1,1,1,2,2,3] and k = 2, return [1,2].

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.

Solution

public class Solution {
     public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int i : nums) {
            count.merge(i, 1, (a, b) -> a + b);
        }

        List<Entity> entities = new ArrayList<>();
        count.entrySet().forEach(
                item -> entities.add(new Entity(item.getKey(), item.getValue()))
        );
        Collections.sort(entities, (a, b) -> -a.count + b.count);

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(entities.get(i).val);
        }
        return result;
    }

    public static class Entity {
        int val;
        int count;

        public Entity(int v, int c) {
            this.val = v;
            this.count = c;
        }
    }
}