-
Notifications
You must be signed in to change notification settings - Fork 0
/
Kth largest and smallest element
60 lines (54 loc) · 1.23 KB
/
Kth largest and smallest element
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <queue>
//Function to sort an array using quick sort algorithm.
int partition (vector <int> &arr, int low, int high)
{
// Your code here
int i = low - 1;
int pivot = arr[high] ;
for(int j = low ; j <= high - 1; j++)
{
if(arr[j] < pivot)
{
i++;
swap(arr[i] , arr[j]);
}
}
swap(arr[high] , arr[i + 1]) ;
return i + 1;
}
void quickSort1(vector <int> &arr , int low, int high , int k , int &ans)
{
// code here
if(low > high)
{
return ;
}
int ind = partition(arr , low , high ) ;
//cout << ind << endl ;
if(ind == k)
{
//cout << ind ;
ans = arr[ind] ;
return ;
}
else if(ind > k)
{
quickSort1(arr , low , ind - 1 , k , ans) ;
}
else
{
quickSort1(arr , ind + 1 , high , k,ans) ;
}
}
vector<int> kthSmallLarge(vector<int> &arr, int n, int k)
{
// Write your code here.
vector <int> ans ;
int ksmall = 0 ;
int klarge = 0 ;
quickSort1(arr, 0 , n - 1, k - 1 , ksmall ) ;
quickSort1(arr , 0 , n - 1 , n - k , klarge);
ans.push_back(ksmall) ;
ans.push_back(klarge) ;
return ans ;
}