ในบทช่วยสอนนี้ เราจะไปหา k-th องค์ประกอบที่เล็กที่สุดหลังจากการแทรกทุกครั้ง
เราจะใช้ min-heap เพื่อแก้ปัญหา มาดูขั้นตอนในการจบโปรแกรมกัน
- เริ่มต้นอาร์เรย์ด้วยข้อมูลสุ่ม
- เริ่มต้นคิวลำดับความสำคัญ
- จนถึง k - 1 จะไม่มี k-th . ใดๆ องค์ประกอบที่เล็กที่สุด ดังนั้น พิมพ์สัญลักษณ์ใดๆ ที่คุณชอบ
- เขียนลูปที่วนซ้ำจาก k + 1 ถึง n.
- พิมพ์รูทของ min-heap
- หากองค์ประกอบมากกว่ารูทของ min-heap ให้เปิดรูทและแทรกองค์ประกอบ
ตัวอย่าง
มาดูโค้ดกันเลย
#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
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
