在 C++ 中每次插入后第 K 个最小元素
在本教程中,我们将在每次插入后找到第k个最小的元素。
我们将使用最小堆来解决这个问题。让我们看看完成该程序的步骤。
用随机数据初始化数组。
初始化优先队列。
直到k-1不会有任何第k个最小元素。所以,打印你喜欢的任何符号。
编写一个循环,从k+1迭代到n。
打印最小堆的根。
如果元素大于最小堆的根,则弹出根并插入元素。
示例
让我们看看代码。
#include输出结果using namespace std; void findKthSmallestElement(int elements[], int n, int k) { priority_queue , greater > queue; for (int i= 0; i < k - 1; i++) { queue.push(elements[i]); cout << "- "; } queue.push(elements[k-1]); for (int i = k; i < n; i++) { cout << queue.top() << " "; if (elements[i] > queue.top()) { queue.pop(); queue.push(elements[i]); } } cout << queue.top() << endl; } int main() { int arr[] = {3, 5, 6, 2, 7, 8, 2, 3, 5, 9}; findKthSmallestElement(arr, 10, 5); return 0; }
如果你运行上面的代码,那么你会得到下面的结果。
- - - - 2 3 3 3 5 5
结论
如果您对本教程有任何疑问,请在评论部分提及。