在 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

结论

如果您对本教程有任何疑问,请在评论部分提及。

以上是 在 C++ 中每次插入后第 K 个最小元素 的全部内容, 来源链接: utcz.com/z/361033.html

回到顶部