Given : An array of numbers.
Objective : To find the k’th largest and k’th smallest number.
| Idea for finding the k’th largest and k’th smallest number |
|---|
| - Create a max heap / min heap using a priority_queue ( C++ ) with the given numbers. - Start popping out the numbers from the max heap till the k’th number is popped out. Similar logic could be used for finding out the k’th smallest number. Instead of creating a max heap, we could create a min heap. |
Time complexity : A max / min heap could be built using a priority_queue ( C++ ) in O ( n ) time. Popping an element out of a heap takes O ( log n ) time. Thus the overall complexity of finding the k’th largest / smallest element is O ( n log n ).
Program
#include<iostream>
#include<queue>
#include<vector>
int Find_Kth_Largest (std :: vector<int>& vec_nums, int k) {
std :: priority_queue<int> pq_maxheap (vec_nums.begin(), vec_nums.end());
int cnt = 1;
while (!pq_maxheap.empty()) {
if (cnt == k) {
return pq_maxheap.top();
}
pq_maxheap.pop();
cnt++;
}
return 0;
}
int Find_Kth_Smallest (std :: vector<int>& vec_nums, int k) {
/* The default template argument to compare template is std::less<T> i.e it is a max heap by default.
For a min heap "std::greater<T>" needs to be passed */
std :: priority_queue<int, std :: vector<int>, std :: greater<int>> pq_minheap (vec_nums.begin(), vec_nums.end());
int cnt = 1;
while (!pq_minheap.empty()) {
if (cnt == k) {
return pq_minheap.top();
}
pq_minheap.pop();
cnt++;
}
return 0;
}
int main() {
std :: vector<int> vec {1, 4, 3, 2, 5, 10, 30, 20, 40, 50};
int k;
for (auto& num: vec) {
std :: cout << num << " ";
}
std :: cout << "\nFinding k'th largest and smallest element in the vector" << std :: endl;
std :: cout << "Enter k between 1 and " << vec.size() << " : ";
std :: cin >> k;
std :: cout << "K'th largest number : " << Find_Kth_Largest(vec, k) << std :: endl;
std :: cout << "K'th smallest number : " << Find_Kth_Smallest(vec, k) << std :: endl;
return 0;
}
Output
1 4 3 2 5 10 30 20 40 50
Finding k'th largest and smallest element in the vector
Enter k between 1 and 10 : 5
K'th largest number : 10
K'th smallest number : 5
1 4 3 2 5 10 30 20 40 50
Finding k'th largest and smallest element in the vector
Enter k between 1 and 10 : 6
K'th largest number : 5
K'th smallest number : 10