← 返回 google 的题目列表Top K Frequent Elements
类型：online_judge
Problem
Given a non-empty integer array nums and an integer k, return the k most frequent elements.
Requirements:
The answer may be returned in any order.
Discuss whether the time complexity can be better than O(N log N).
Follow-up: how can you optimize the space complexity?
Input Format
The first line contains two integers n and k.
The second line contains n integers representing nums.
Output Format
Print k integers representing the most frequent elements. For deterministic judging, output them using this order:
Higher frequency first;
If frequencies tie, smaller value first.
Constraints
1 <= n <= 10^5
1 <= k <= number of distinct elements
-10^9 <= nums[i] <= 10^9
Example
Input:
6 2
1 1 1 2 2 3
Output:
1 2
Example
Input
6 2
1 1 1 2 2 3
Output
1 2