Computer >> Máy Tính >  >> Lập trình >> C ++

Phần tử nhỏ nhất thứ K sau mỗi lần chèn trong C ++

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

Chúng tôi sẽ sử dụng min-heap để giải quyết vấn đề. Hãy xem các bước để hoàn thành chương trình.

  • 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.
  • Cho đến k - 1 sẽ không có bất kỳ k-th nào phần tử nhỏ nhất. Vì vậy, hãy in bất kỳ ký hiệu nào bạn thích.
  • Viết một vòng lặp lặp lại từ k + 1 đến n.
    • In phần gốc của min-heap.
    • Nếu phần tử lớn hơn phần tử gốc của min-heap, hãy mở phần tử gốc và chèn phần tử.

Ví dụ

Hãy xem mã.

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

Đầu ra

Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.

- - - - 2 3 3 3 5 5

Kết luận

Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.