Q.) FIND THE KTH SMALLEST ELEMENT IN A GIVEN ARRAY .
SOLUTION--
#include
#include
using namespace std;
int main()
{
int n,k,i,min;
printf("enter the size of array=");
scanf("%d",&n);
int arr[n];
printf("the velue of k=");
scanf("%d",&k);
for(i=0;i
scanf("%d",&arr[i]);
sort(arr,arr+k);
min=arr[k-1];
for(i=k;i
{
if(arr[i]
{
arr[k-1]=arr[i];
sort(arr,arr+k);
min=arr[k-1];
}
}
printf("%dth smallest element in array=%d",k,arr[k-1]);
return 0;
}
1 comment:
EXPLAINATION--
Step 1 From first K numbers build a max heap so that the top element is largest in those K numbers. Say that element is X.
Step 2 Now as numbers are coming for processing, say coming number be A
If A>X then A cant be Kth smallest.
If A=X then no change is needed.
If A6 so we will neglect 8. When 3 will come since 3<6 we will replace 6 with 3 in the heap and again we will call heapify. After heapify 5 will be on the top. When 2 will come, 2<5 then 5 will be replaced by 2 and after heapification 3 will be on the top. When 4 will come since 4>3 then we will neglect the 4. Now at the end 3 is on the top of the heap so 3 is the3rd smalle st element of the given numbers or array.
NOTE-For Kth largest build min heap
Post a Comment