Top K Frequent Elements
Google● MediumNEW GRADPHONE SCREENProblem statement
Given a non-empty integer array nums and an integer k, return the k values that occur most frequently.
Order the result by decreasing frequency. When two values have the same frequency, the value whose first occurrence in nums appears earlier comes first.
Design an approach that improves on sorting all n input elements in O(n log n) time, and be prepared to discuss the space trade-offs.
Function
topKFrequent(nums: int[], k: int) → int[]Examples
Example 1
nums = [1,1,1,2,2,3]k = 2return = [1,2]1 occurs three times and 2 occurs twice, so they are the two most frequent values.
Example 2
nums = [4,6,4,6,5]k = 2return = [4,6]4 and 6 both occur twice. The first 4 appears before the first 6, so 4 wins the tie.
Example 3
nums = [-1,-1,2,3,2,3]k = 3return = [-1,2,3]All three values occur twice, so their first-occurrence positions determine the complete result order.
Constraints
1 <= nums.length <= 100000.-1000000000 <= nums[i] <= 1000000000.1 <= k <=the number of distinct values innums.- Return exactly
kdistinct values in the required order.