71. Most Talked About
A community forum logs one topic id for every post, and the ids collected over a week are stored in the array nums. The moderators want a leaderboard showing which topics got the most posts.
Return an array containing the k topic ids that occur most often in nums, listed from the most frequent to the least frequent. If two ids occur the same number of times, the smaller id is listed first. If nums holds fewer than k distinct ids, return every distinct id in that same order. The order of the returned array is fixed, so it must match exactly.
Example 1
- Input:
- nums = [7,7,3,3,3,9,9,1], k = 2
- Output:
- [3,7]
- Explanation:
Id 3 occurs three times, while 7 and 9 both occur twice and 7 is smaller, so the answer is [3,7].
Example 2
- Input:
- nums = [5,-2,-2,8], k = 3
- Output:
- [-2,5,8]
- Explanation:
-2 occurs twice; 5 and 8 occur once each, so they follow in increasing order.
Constraints
1 ≤ nums.length ≤ 106
-109 ≤ nums[i] ≤ 109
1 ≤ k ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n log k)
- Space
- O(n)