347. Top K Frequent Elements

寻找一个数组中出现频率从高到低的k个元素

思路：map，pq，注意调用API

1.map + sort: O(n) + O(nlogn)

public List<Integer> topKFrequent(int[] nums, int k) {
    // boundary check: if nums is null or length == 0; then must return null to avoid nullpointerexception when adding elements to the list
    // if k < 0: can be returned
    // if k == 0: similar to k < 0, but it makes no sense
    if (nums == null || nums.length == 0 || k <= 0) return null;

    // put elements into map
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }

    // boundary check again
    if (k > map.size()) return null;

    // put entries into a list
    List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(map.entrySet());

    // sort list by comparator, faster than no reversed()
    entries.sort(Map.Entry.<Integer, Integer>comparingByValue().reversed());

    // return result
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        res.add((int) entries.get(i).getKey());
    }
    return res;
}

2.priority queue(min heap): O(nlogk), used when k much less than n

public List<Integer> topKFrequent(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k <= 0) return null;

    // count frequencies by map, use foreach
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : nums) {
        map.put(i, map.getOrDefault(i, 0) + 1);
    }

    // boundary check again
    if (k > map.size()) return null;

    // create a priority queue(min heap with regard to map.values())
    PriorityQueue<Map.Entry<Integer, Integer>> q = 
        new PriorityQueue<>(Map.Entry.comparingByValue());
    for (Map.Entry e : map.entrySet()) {
        q.offer(e);
        if (q.size() > k) 
            q.poll();
    }

    // create result list
    List<Integer> res = new ArrayList<>();
    for (Map.Entry e : q) {
        res.add((int)e.getKey());
    }
    return res;
}

3.priority queue(max heap): O(nlog(n - k)), used when k is almost equal to n

public List<Integer> topKFrequent(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k <= 0) return null;

    // count frequencies by map
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : nums) {
        map.put(i, map.getOrDefault(i, 0) + 1);
    }

    // boundary check again
    if (k > map.size()) return null;

    // create result list
    List<Integer> res = new ArrayList<>();

    // create a priority queue(max heap)
    PriorityQueue<Map.Entry<Integer, Integer>> q = 
        new PriorityQueue<>(Map.Entry.<Integer, Integer>comparingByValue().reversed()); // n - k
    for (Map.Entry e : map.entrySet()) {
        q.offer(e);
        if (q.size() > map.size() - k) // get elements excluded from max heap 
            res.add((int)q.poll().getKey());
    }
    return res;
}