🚩 题目链接
⛲ 题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
🌟 求解思路&实现代码&运行结果
⚡ 模拟
🥦 求解思路
- 统计元素频次：首先创建一个HashMap，遍历给定的整数数组nums，对于数组中的每个元素，检查其是否已存在于HashMap中。若已存在，就将该元素对应的频次值加1；若不存在，则将该元素添加进HashMap，并将其频次初始化为1，以此完成对数组中所有元素出现频次的统计。
- 按照频次分组存放元素：创建一个长度为nums.length + 1的ArrayList类型数组list，其目的是可以使用元素的频次作为索引来存放相应元素。接着遍历之前统计频次的HashMap，根据每个元素对应的频次值i，将元素添加到list[i]中。若list[i]还未初始化（即为null），则先创建一个新的ArrayList，再添加元素，从而实现按照频次对元素进行分组存放。
- 获取前k个高频元素：从list数组的末尾（即频次最高的位置）开始，按逆序依次遍历每个元素列表所在位置。只要存放结果的List集合res中元素个数还小于k，就对当前位置的元素列表进行检查，若不为空，则将该列表中的所有元素添加到res中，这样不断添加，直至res中包含了出现频率前k高的元素为止。
- 结果转换为数组返回：创建一个长度与res集合元素个数相等的int类型数组ans，然后通过遍历res集合，将其中的每个元素依次赋值给ans数组的对应位置，最后返回ans数组，得到出现频率前k高的元素组成的数组结果。
- 有了基本的思路，接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {
public int[] topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList();
HashMap<Integer, Integer> map = new HashMap();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
List<Integer>[] list = new ArrayList[nums.length + 1];
for (int key : map.keySet()) {
int i = map.get(key);
if (list[i] == null) {
list[i] = new ArrayList();
}
list[i].add(key);
}
for (int i = list.length - 1; i >= 0 && res.size() < k; i--) {
if (list[i] == null)
continue;
res.addAll(list[i]);
}
int[] ans = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
ans[i] = res.get(i);
}
return ans;
}
}