面试系列 - 高级数据结构
文章目录
数据结构也是有高低级之分的
数据结构
优先队列
与普通队列的区别:
保证每次取出的元素是队列中优先级最高的,有限级别可以自定义。
本质:
二叉堆的结构,利用一个数组结构来实现完全二叉树。
特性:
数组里的第一个元素array[0]拥有最高的优先级
给定一个下标i,那么对于元素array[i]而言
父节点 对应的元素下标是(i-1)/2
左侧子节点 对应的元素下标是2*i + 1
右侧子节点 对应的元素下标是2*i + 2
数组中的每个元素的优先级都必须要高于它两侧子节点
例题
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
说明:
你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
public static List<Integer> topKFrequent(int[] nums, int k) {
// 首先我们需要先通过map将数据进行整理
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
int a = map.get(num) == null ? 0 : map.get(num);
map.put(num, a + 1);
}
// 使用优先队列进行数据的整理,优先队列默认排序是从高到低的
Queue<Integer> queue = new PriorityQueue<>(
// 按照出现频率从低到高排序
Comparator.comparingInt(map::get)
);
// 需要将数据循环放入优先队列中,如果超过k个的话就弹出最上面的
for (Integer a : map.keySet()) {
queue.add(a);
if (queue.size() > k) {
queue.poll();
}
}
List<Integer> list = new ArrayList<>(k);
// 循环添加k个值进入list中,返回即可
while (!queue.isEmpty()) {
list.add(queue.poll());
}
return list;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论