class KthLargest { int K; priority_queue<int, vector<int>, greater<int>> pq; public: KthLargest(int k, vector<int>& nums) { for (int n : nums) { pq.push(n); if (pq.size() > k) pq.pop(); } K = k; } int add(int val) { pq.push(val); if (pq.size() > K) pq.pop(); return pq.top(); } }; 解释这段代码
时间: 2024-04-11 14:30:40 浏览: 88
UART_INT.zip_UART_INT_uart int
这段代码是一个类`KthLargest`的实现,用于找到第K大的元素。它使用了一个最小堆(`priority_queue`)来维护当前最大的K个元素。
在类的构造函数中,通过循环遍历给定的整数数组`nums`,将每个元素插入到最小堆中。如果最小堆的大小超过了K,就将堆顶元素弹出,以保持堆的大小为K。这样,构造函数结束后,最小堆中就保存了数组中最大的K个元素。
`add`函数用于向已构建的堆中添加新的元素`val`。首先将`val`插入到堆中,然后判断堆的大小是否超过了K。如果超过了K,就弹出堆顶元素,以保持堆的大小为K。最后,返回当前堆顶元素,即为第K大的元素。
使用这个类,我们可以先构造一个KthLargest对象,并传入初始的K和一组初始数字数组。然后通过调用`add`方法不断地添加新的元素,并可以每次得到当前第K大的元素。
总而言之,这段代码通过使用最小堆来实现了找到第K大的元素,并提供了添加新元素的功能。
阅读全文