使用优先队列查找无序数组中的第 K 小元素

---

优先队列是一种基于堆的数据结构，它以这样一种方式存储元素，使得最大或最小元素始终位于顶部。给定一个无序数组，我们需要使用优先队列从中找到第 K 小的元素。这里，元素 k 将被给出，并且必须在 1 到给定数组大小的范围内。

示例

让我们借助输入-输出示例来理解这个问题：

输入

int arr[] = {1, 5, 6, 2, 3, 6, 7, 9, 12, 15, 0, 8}
int k = 4

输出

3

解释

在给定的数组中，对数组排序后，我们将得到 3 作为数组的第 4 小元素。

方法 1

在这种方法中，我们将创建一个函数，该函数将给定的数组和数字作为参数，并将第 k 个最小元素作为返回值。

我们将遍历数组，并在 N * log(N) 时间内将数组的所有元素填充到优先队列中。

然后，我们将移除优先队列中的所有元素，直到其大小变为 k，我们将使用 while 循环和优先队列的 pop() 方法来执行此操作。

最后，我们将返回大小为 K 的优先队列的顶部元素，因为它将是所需的数字。

示例

#include <bits/stdc++.h>
using namespace std;

// function to get the kth smallest element 
int findNumber(vector<int>& arr, int k){
   // defining priority queue 
   priority_queue<int>pq;    
   // adding all the elements of the given array to it
   int len = arr.size();
   for(int i=0; i<len; i++){
      pq.push(arr[i]);
   }    
   // now size of the priority queue is N
   // remove all the elements until size is K
   while(pq.size() > k){
      pq.pop();
   }
   // return the final answer 
   return pq.top();
}
int main(){
   vector<int> arr = {1, 5, 6, 2, 3, 6, 7, 9, 12, 15, 0, 8};
   int k = 4; // given k 
   // calling the function 
   cout<< " The kth smallest number in the given array is: " << findNumber(arr,k) << endl;
   return 0;
}

输出

The kth smallest number in the given array is: 3

时间和空间复杂度

以上代码的时间复杂度为 O(N*log(N))，其中 N 是给定数组的大小。

以上代码的空间复杂度为 O(N)，因为我们使用了最大大小为 N 的优先队列。

方法 2

这种方法类似于前一种方法，但区别在于它只需要较少的时间复杂度（K 的对数因子），并且优先队列的大小也将是 K，而不是 N。

我们将遍历数组，并将数组的所有元素添加到优先队列中，直到优先队列的大小小于 K。

之后，我们将检查当前数组元素是否大于优先队列的顶部元素，如果是，则可以忽略当前元素，因为队列中已经存在较小的元素。

如果当前元素小于顶部元素，则顶部元素是优先队列中所有 K 个元素中最大的，因此我们将删除顶部元素并将当前元素添加到优先队列中。

最后，我们将返回优先队列的顶部元素，因为它在所有元素中最大。

示例

#include <bits/stdc++.h>
using namespace std;

// function to get the k-th smallest element 
int findNumber(vector<int>& arr, int k){
   // defining priority queue 
   priority_queue<int>pq;
    
   // adding all the elements of the given array to the priority queue 
   int len = arr.size();
   for(int i=0; i<len; i++){
      if(pq.size() < k){
         // if total number of elements in the priority queue is less than k
         // then add this element to the queue
         pq.push(arr[i]);
      } else if(pq.top() < arr[i]){
         // if the top element of the priority queue is smaller than this current element. then just move to the next element
         continue;
      } else {
         // else add this element to the queue 
         pq.pop();
         pq.push(arr[i]);
      }
   }
   return pq.top();
}
int main(){
   // given array
   vector<int> arr = {1, 5, 6, 2, 3, 6, 7, 9, 12, 15, 0, 8};
   int k = 4; // given k 
   // calling the function 
   cout<<"The kth smallest number in the given array is: "<<findNumber(arr,k)<<endl;
   return 0;
}

输出

The kth smallest number in the given array is: 3

时间和空间复杂度

以上代码的时间复杂度为 O(N*log(K))，其中 N 是给定数组的大小，K 是给定的数字，此对数因子是由于优先队列，并且其大小最多可以达到 k。

以上代码的空间复杂度为 O(K)，因为我们只在优先队列中存储最大 k 个元素。

结论

在本教程中，我们实现了一个程序，通过使用优先队列从给定数组中找到第 K 小的元素。优先队列是一种基于堆的数据结构，它将最小或最大元素存储在顶部。我们已经实现了两个程序，第一个程序的时间复杂度为 O(N*log(N))，空间复杂度为 O(N)，而第二个程序在时间和空间复杂度中都具有 K 的因子。