C++程序 在数据流中查找第k大元素
给定一个无限的整数流,查找任何时刻的第k大元素。
例子:
输入:
stream[] = {10, 20, 11, 70, 50, 40, 100, 5, …}
k = 3
输出: {_, _, 10, 11, 20, 40, 50, 50, …}
允许的额外空间为O(k)。
一个 简单的解决方案 是保持大小为k的数组。想法是让数组排序,以便可以在O(1)时间内找到第k大的元素(如果数组按增量顺序排序,我们只需返回数组的第一个元素)。
如何处理流的新元素?
对于流中的每个新元素,请检查新元素是否小于当前的第k大元素。如果是,则忽略它。否则,从数组中删除最小元素并以排序顺序插入新元素。处理新元素的时间复杂度为O(k)。
一个 更好的解决方案 是使用大小为k的自平衡二叉搜索树。可以在O(Logk)时间内找到第k大的元素。
如何处理流的新元素?
对于流中的每个新元素,请检查新元素是否小于当前的第k大元素。如果是,则忽略它。否则,从树中删除最小元素并插入新元素。处理新元素的时间复杂度为O(Logk)。
一个 高效的解决方案 是使用大小为k的小根堆来存储流的k个最大元素。第k大的元素始终位于根处,并且可以在O(1)时间内找到它。
如何处理流的新元素?
将新元素与堆的根进行比较。如果新元素较小,则忽略它。否则,将根替换为新元素并对修改后的堆的根进行堆化调用。找到第k大的元素的时间复杂度为O(Logk)。
// 在流中找到第k小的元素的C++程序
#include <climits>
#include <iostream>
using namespace std;
// 交换两个整数的实用函数的原型
void swap(int* x, int* y);
// MinHeap类
class MinHeap {
int* harr; // 指向堆中元素数组的指针
int capacity; // 最小堆的可能最大尺寸
int heap_size; // 目前最小堆中的元素数量
public:
MinHeap(int a[], int size); //构造函数
void buildHeap();
void MinHeapify(
int i); // 对以索引i为根的子树进行最小堆堆化
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2 * i + 2); }
int extractMin(); // 抽取根节点(最小)元素
int getMin() { return harr[0]; }
// 用新节点x替换根节点并堆化新节点
void replaceMin(int x)
{
harr[0] = x;
MinHeapify(0);
}
};
MinHeap::MinHeap(int a[], int size)
{
heap_size = size;
harr = a; // 存储数组的地址
}
void MinHeap::buildHeap()
{
int i = (heap_size - 1) / 2;
while (i >= 0) {
MinHeapify(i);
i--;
}
}
// 从最小堆中删除最小的元素(或根)
int MinHeap::extractMin()
{
if (heap_size == 0)
return INT_MAX;
// 存储最小值
int root = harr[0];
// 如果有多于1个元素,
// 将最后一个元素移到根并调用heapify
if (heap_size > 1) {
harr[0] = harr[heap_size - 1];
MinHeapify(0);
}
heap_size--;
return root;
}
// 对以指定索引为根的子树进行堆化的递归方法,假设子树已经堆化
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i) {
swap(↔[i], ↔[smallest]);
MinHeapify(smallest);
}
}
// 交换两个元素的实用函数
void swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// 返回输入数据流中第k大的元素的函数
void kthLargest(int k)
{
// count是迄今为止在流中看到的元素的总数
int count = 0, x; // x是新元素
// 创建大小为k的最小堆
int* arr = new int[k];
MinHeap mh(arr, k);
while (1) {
// 从流中获取下一个元素
cout << "输入下一个流元素 ";
cin >> x;
// 对于前k-1个元素,没有什么要做的
if (count < k - 1) {
arr[count] = x;
count++;
}
else {
// 如果这是第k个元素,则将其存储起来,
// 并建立上面创建的堆。
if (count == k - 1) {
arr[count] = x;
mh.buildHeap();
}
else {
// 如果下一个元素比第k大的元素大,则替换根
if (x > mh.getMin())
mh.replaceMin(x); // replaceMin调用heapify()
}
// 堆根是第k大元素
cout << "第k大的元素是 "
<< mh.getMin() << endl;
count++;
}
}
}
// 测试以上方法的驱动程序
int main()
{
int k = 3;
cout << "k是 " << k << endl;
kthLargest(k);
return 0;
}
输出:
K是3
输入流的下一个元素23
输入流的下一个元素10
输入流的下一个元素15
第k大的元素是10
输入流的下一个元素70
第k大的元素是15
输入流的下一个元素5
第k大的元素是15
输入流的下一个元素80
第k大的元素是23
输入流的下一个元素100
第k大的元素是70
输入流的下一个元素
按了CTRL + C
时间复杂度: O(N * log K)
使用优先队列实现:
//上面的方法的 C++ 实现
#include <bits/stdc++.h>
using namespace std;
vector<int> kthLargest(int k, int arr[], int n)
{
vector<int> ans(n);
//使用优先队列创建最小堆
priority_queue<int, vector<int>, greater<int> > pq;
//遍历每个元素
for (int i = 0; i < n; i++) {
//如果优先队列的大小小于 k
if (pq.size() < k)
pq.push(arr[i]);
else {
if (arr[i] > pq.top()) {
pq.pop();
pq.push(arr[i]);
}
}
//如果数量小于 k
if (pq.size() < k)
ans[i] = -1;
else
ans[i] = pq.top();
}
return ans;
}
//主函数
int main()
{
int n = 6;
int arr[n] = { 1, 2, 3, 4, 5, 6 };
int k = 4;
//函数调用
vector<int> v = kthLargest(k, arr, n);
for (auto it : v)
cout << it << " ";
return 0;
}
输出
-1 -1 -1 1 2 3
时间复杂度: O(N * log K)
辅助空间: O(K)