Program 9 - Kth smallest/largest element in Array | Competitive Programming in C++

Publié le: 01 janvier 1970
sur la chaîne: Prateek Jain Academy

705

K’th Smallest/Largest Element in Unsorted Array

Download our App : - https://eduthanos.page.link/t2yA

Contact No - 9555031137

www.PrateekJainAcademy.com

Given an array and a number K where K is smaller than the size of the array. Find the K’th smallest element in the given array. Given that all array elements are distinct.

Examples:

Input: arr[] = {7, 10, 4, 3, 20, 15}, K = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}, K = 4
Output: 10

K’th smallest element in an unsorted array using sorting:
Sort the given array and return the element at index K-1 in the sorted array.

Follow the given steps to solve the problem:

Sort the input array in the increasing order
Return the element at the K-1 index (0 – Based indexing) in the sorted array

K’th smallest element in an unsorted array using set data structure:
Set data structure can be used to find the kth smallest element as it stores the distinct elements in sorted order. Set can be used because it is mentioned in the question that all the elements in the array are distinct.

Follow the given steps to solve the problem:

Insert all array elements into the set
Advance the iterator to the Kth element in the set
Return the value of the element at which the iterator is pointing

K’th smallest element in an unsorted array using Min-Heap
Min-Heap can be used to find the kth smallest element, by inserting all the elements into Min-Heap and then and call extractMin() function K times.

Follow the given steps to solve the problem:

Insert all the array elements into the Min-Heap
Call extractMin() function K times
Return the value obtained at the last call of extractMin() function

Max-Heap can be used to find the kth smallest element, by inserting first K elements into Max-Heap and then compare remaining elements with the root of the Max-Heap and if the element is less than the root then remove the root and insert this element into the heap and finally return root of the Max-Heap

Follow the given steps to solve the problem:

Build a Max-Heap MH of the first K elements (arr[0] to arr[K-1]) of the given array.
For each element, after the Kth element (arr[K] to arr[n-1]), compare it with the root of MH.
If the element is less than the root then make it the root and call heapify for Max-Heap MH
b) Else ignore it.
Finally, the root of the MH is the Kth smallest element.

To find the Kth minimum element in an array, insert the elements into the priority queue until the size of it is less than K, and then compare remaining elements with the root of the priority queue and if the element is less than the root then remove the root and insert this element into the priority queue and finally return root of the priority queue

Follow the given steps to solve the problem:

Build a priority queue of the first K elements (arr[0] to arr[K-1]) of the given array.
For each element, after the Kth element (arr[K] to arr[n-1]), compare it with the root of priority queue.
If the element is less than the root then remove the root and insert this element into the priority queue
b) Else ignore it.
Finally, the root of the priority queue is the Kth smallest element.

Sur cette page du site, vous pouvez voir la vidéo en ligne Program 9 - Kth smallest/largest element in Array | Competitive Programming in C++ durée heure minute seconde en bonne qualité , qui a été Téléchargé par l'utilisateur Prateek Jain Academy 01 janvier 1970, Partagez le lien avec vos amis et connaissances, sur youtube cette vidéo a déjà été regardée 705 fois et il a aimé 19 téléspectateurs. Bon visionnage!