347. Top K Frequent Elements (Medium)

https://leetcode.com/problems/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.

Solutions

class Solution {

    // Sort the elements by its frequency in given array.

    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();

        if (nums == null || nums.length == 0) {
            return ans;
        }

        // Figure out the count of each unique number
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int n : nums) {
            if (!countMap.containsKey(n)) {
                countMap.put(n, 0);
            }

            countMap.put(n, countMap.get(n) + 1);
        }

        // The time complexity of sorting operation is O(nlogn)
        Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> countMap.get(o2) - countMap.get(o1));

        for (Integer key : countMap.keySet()) {
            queue.add(key);
        }

        int preCount = 0;
        for (int i = 0; i < k; i++) {
            int num = queue.poll();
            ans.add(num);
            preCount = countMap.get(num);
        }

        // These elements of same count must be included.
        while (!queue.isEmpty() && preCount == countMap.get(queue.peek())) {
            ans.add(queue.poll());
        }

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-22 00:37:51

results matching ""

    No results matching ""