[Leetcode] Top K Frequent Elements
Published in
Feb 7, 2022
Use partial sorting to outperform O(nlogn).
Description
Given an integer array nums
and an integer k
, return the k
most frequent elements. You may return the answer in any order.
Examples
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Solution
Heapq in python keeps the smallest being the root. Therefore, by popping root when already pushing k elements, only top k would be kept. Notice that pop() is O(log n), fast enought to pass the requirment .
- code
ref: