หาค่าน้อยที่สุดลำดับที่ k หลังจากการแทรกทุกครั้งใน C++

ในบทช่วยสอนนี้ เราจะหาค่า k-th น้อยที่สุดหลังจากการแทรกข้อมูลทุกครั้ง

เราจะใช้ min-heap เพื่อแก้ปัญหา มาดูขั้นตอนการเขียนโปรแกรม

• กำหนดค่าเริ่มต้นของอาร์เรย์ด้วยข้อมูลสุ่ม
• กำหนดค่าเริ่มต้นของ priority queue
• จนถึง k - 1 จะยังไม่มีค่า k-th น้อยที่สุด ดังนั้นให้พิมพ์สัญลักษณ์ที่ต้องการ
• เขียนลูปที่วนจาก k + 1 ถึง n
  • พิมพ์ค่ารากของ min-heap
  • ถ้าองค์ประกอบมากกว่ารากของ min-heap ให้ pop รากและแทรกองค์ประกอบนั้น

ตัวอย่างโค้ด

#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

สรุป

หากมีข้อสงสัยเกี่ยวกับบทช่วยสอนนี้ สามารถถามได้ในส่วนความคิดเห็น