Tìm phần tử K-th nhỏ nhất sau mỗi lần chèn trong C++

Trong hướng dẫn này, chúng ta sẽ tìm phần tử K-th nhỏ nhất sau mỗi lần chèn.

Chúng ta sẽ sử dụng min-heap (hàng đợi ưu tiên nhỏ nhất) để giải quyết bài toán. Hãy xem các bước thực hiện.

• Khởi tạo mảng với dữ liệu ngẫu nhiên.
• Khởi tạo hàng đợi ưu tiên.
• Đến K - 1 phần tử đầu tiên sẽ chưa có phần tử K-th nhỏ nhất. In ký hiệu tùy ý (ví dụ '-').
• Viết vòng lặp từ K đến N:
  • In phần tử gốc của min-heap.
  • Nếu phần tử hiện tại lớn hơn gốc min-heap, loại bỏ gốc và chèn phần tử mới.

Ví dụ

Dưới đây là mã nguồn C++:

#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; 
}

Kết quả

Nếu bạn chạy mã trên, kết quả sẽ là:

- - - - 2 3 3 3 5 5

Kết luận

Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.