Top K Frequent Elements
Microsoft● MediumFULLTIMEPHONE SCREENProblem statement
Given an integer array nums and an integer k, return the k distinct values that occur most frequently.
For this exercise, order values by decreasing frequency. If two values have equal frequency, put the value whose first occurrence appears earlier in nums first. Return exactly k values in that order.
After solving, compare a size-k heap with a frequency-bucket approach. Explain how their time and space costs differ.
Function
topKFrequentElements(nums: int[], k: int) → int[]Examples
Example 1
nums = [1,1,1,2,2,3]k = 2return = [1,2]Value 1 appears three times and value 2 appears twice.
Example 2
nums = [4,5,4,5,6]k = 2return = [4,5]Values 4 and 5 tie at two occurrences; 4 appeared first.
Example 3
nums = [-3,-3,7,7,7,-3,9]k = 2return = [-3,7]Values -3 and 7 each appear three times. The first -3 precedes the first 7.
Constraints
1 <= nums.length <= 100000.- Each value is a signed 32-bit integer.
1 <= k <=the number of distinct values innums.