C++ 使用优先队列找到未排序数组中的第k小元素

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

示例

让我们通过输入输出示例来理解问题：

输入

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

输出

3

说明

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

方法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，而不是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(Nlog(K))，其中N是给定数组的大小，K是给定的数字，log因子是由于优先队列，其大小最大可以达到k。

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

结论

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