使用優先佇列查詢無序陣列中的第 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 的因子。