Program 9 - Kth smallest/largest element in Array | Competitive Programming in C++
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.
Auf dieser Seite können Sie das Online-Video Program 9 - Kth smallest/largest element in Array | Competitive Programming in C++ mit der Dauer stunde minuten sekunde in guter Qualität ansehen, das der Benutzer Prateek Jain Academy 01 Januar 1970 hochgeladen hat, den Link mit Freunden und Bekannten teilen, dieses Video wurde auf Youtube bereits 705 Mal angesehen und es wurde von 19 den Zuschauern gefallen. Viel Spaß beim Betrachtenden Zuschauern gefallen!
