9.2 堆应用
...大约 4 分钟
堆的特点是最大/小值位于顶部, 获取最值的时间复杂度为O(1). 插入和删除操作时间复杂度为O(logn).
堆可以用于求动态数据集合中的最值:
- 最大堆: 获取数据集合中最小的k个元素
- 最小堆: 获取数据集合中最大的k个元素
9.2.1 问题59: 数据流的第k大数字
设计一个找到数据流中第
k
大元素的类(class)。注意是排序后的第k
大元素,不是第k
个不同的元素。请实现
KthLargest
类:
KthLargest(int k, int[] nums)
使用整数k
和整数流nums
初始化对象。int add(int val)
将val
插入数据流nums
后,返回当前数据流中第k
大的元素。示例:
输入: ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出: [null, 4, 5, 5, 8, 8] 解释: KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8
提示:
1 <= k <= 10^4
0 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
-10^4 <= val <= 10^4
- 最多调用
add
方法10^4
次- 题目数据保证,在查找第
k
大元素时,数组中至少有k
个元素
9.2.1.1 分析&题解
找出k个最大数字, 那么第k大的数字就是k个数中最小的那个.
可以将k个数字放入堆中, 对于最小堆和新节点:
- 堆中元素数目小于k, 直接插入
- 堆已满:
- 新节点大于堆顶元素, 删除堆顶元素, 插入新节点
- 新节点小于等于, 则不做任何操作
type KthLargest struct {
minHeap *minIntHeap
size int
}
func Constructor(k int, nums []int) KthLargest {
mh := &minIntHeap{}
kl := &KthLargest{
minHeap: mh,
size: k,
}
for _, n := range nums {
kl.Add(n)
}
return *kl
}
func (kl *KthLargest) Add(val int) int {
if kl.minHeap.Len() < kl.size {
heap.Push(kl.minHeap, val)
} else if val > (*kl.minHeap)[0] {
heap.Pop(kl.minHeap)
heap.Push(kl.minHeap, val)
}
return (*kl.minHeap)[0]
}
// 最小堆
type minIntHeap []int
func (mh minIntHeap) Len() int {
return len(mh)
}
func (mh minIntHeap) Less(i, j int) bool {
return mh[i] < mh[j]
}
func (mh minIntHeap) Swap(i, j int) {
mh[i], mh[j] = mh[j], mh[i]
}
func (mh *minIntHeap) Push(x any) {
*mh = append(*mh, x.(int))
}
func (mh *minIntHeap) Pop() any {
x := (*mh)[len(*mh)-1]
*mh = (*mh)[:len(*mh)-1]
return x
}
9.2.2 问题60: 出现频率最高的k个数字
给定一个整数数组
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
是数组大小。
9.2.2.1 分析&题解
需要统计频次, 可以使用哈希表(数字, 次数), 扫描一次之后就能记录所有的数字出现频次.
再次扫描哈希表, 之后使用最小堆来存储次数最大的k个数字即可.
TC: O(nlogk), k 为最小堆长度
SC: O(n), 需要一个哈希表和一个最小堆
func topKFrequent(nums []int, k int) []int {
res := []int{}
m := map[int]int{}
for _, n := range nums {
m[n]++
}
pq := &PriorityQueue{}
for n, fre := range m {
nf := &numFre{
val: n,
fre: fre,
}
if pq.Len() < k {
heap.Push(pq, nf)
} else if nf.fre > (*pq)[0].fre {
heap.Pop(pq)
heap.Push(pq, nf)
}
}
for _, nf := range *pq {
res = append(res, nf.val)
}
return res
}
type numFre struct {
val int
fre int
index int
}
type PriorityQueue []*numFre
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].fre < pq[j].fre
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PriorityQueue) Push(x any) {
idx := len(*pq)
nf := x.(*numFre)
nf.index = idx
*pq = append(*pq, nf)
}
func (pq *PriorityQueue) Pop() any {
x := (*pq)[len(*pq)-1]
(*pq)[len(*pq)-1] = nil // avoid memory leak
x.index = -1 // for safety
*pq = (*pq)[:len(*pq)-1]
return x
}
9.2.3 问题61: 和最小的k对数
给定两个以升序排列的整数数组
nums1
和nums2
, 以及一个整数k
。定义一对值
(u,v)
,其中第一个元素来自nums1
,第二个元素来自nums2
。请找到和最小的
k
个数对(u1,v1)
,(u2,v2)
...(uk,vk)
。示例 1:
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 输出: [1,2],[1,4],[1,6] 解释: 返回序列中的前 3 对数: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:
输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 输出: [1,1],[1,1] 解释: 返回序列中的前 2 对数: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
示例 3:
输入: nums1 = [1,2], nums2 = [3], k = 3 输出: [1,3],[2,3] 解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
提示:
1 <= nums1.length, nums2.length <= 10^4
-10^9 <= nums1[i], nums2[i] <= 10^9
nums1
,nums2
均为升序排列1 <= k <= 1000
9.2.3.1 分析&题解
// TODO: 2023-09-13
Reference
Powered by Waline v2.15.2