資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究每次插入後 C++ 中的第 k 個最小元素
在本教程中，我們將介紹如何在每次插入後找到第 k 個最小元素。
我們將使用最小堆來解決這個問題。我們來看一下完成此程式的步驟。
- 利用隨機資料初始化陣列。
- 初始化優先順序佇列。
- 直到 k - 1，將不會有任何第 k 個最小元素。因此，列印您喜歡的任何符號。
- 編寫一個迴圈，該迴圈從 k + 1 迭代到 n。
- 列印最小堆的根元素。
- 如果元素大於最小堆的根元素，則彈出根元素並插入該元素。
示例
我們來看一下程式碼。
#include <bits/stdc++.h>
using namespace std;
void findKthSmallestElement(int elements[], int n, int k) {
priority_queue<int, vector<int>, greater<int>> 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
結論
如果您對本教程有任何疑問，請在評論部分中提出。
更新於： 2021 年 4 月 9 日
177 次檢視
廣告