Hello Everyone,
Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array.
Examples:
Input : arr[] = {7, 10, 4, 3, 20, 15} k = 2 Output : 4 Smallest element is 3. Second smallest is 4. Input : arr[] = {7, 10, 4, 3, 3, 15} k = 2 Output : 4 Even if there are more than one occurrences of 3, answer should be 4. Input :arr[] = {7, 10, 4, 3, 20, 15} k = 4 Output : 10
We use set in C++ STL.
- Insert all elements into a set.
- Traverse the set and print k-th element.
// STL based C++ program to find k-th smallest
// element.
#include <bits/stdc++.h>
using
namespace
std;
int
kthSmallest(
int
arr[],
int
n,
int
k)
{
// Insert all elements into the set
set<
int
> s;
for
(
int
i = 0; i < n; i++)
s.insert(arr[i]);
// Traverse set and print k-th element
auto
it = s.begin();
for
(
int
i = 0; i < k - 1; i++)
it++;
return
*it;
}
int
main()
{
int
arr[] = { 12, 3, 5, 7, 3, 19 };
int
n =
sizeof
(arr) /
sizeof
(arr[0]), k = 2;
cout <<
"K'th smallest element is "
<< kthSmallest(arr, n, k);
return
0;
}
Output:
K’th smallest element is 5
Time complexity of above solution is O(n Log n). Note that set in STL uses a self-balancing BST internally and therefore time complexity of search and insert operations is O(log n).