Objective: Given an array of integers. find the Kth Smallest/largest element in the array.
Example:
int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 };
K=4. 4th smallest element in given array: 10
Approach: (Kth Smallest Element)
- Use min-Heap. (Click here to read about Priority Queue).
- Insert all the elements in the Priority Queue.
- Extract K elements from the priority queue. The last element (kth) extracted with be the kth smallest element in the array.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.PriorityQueue; | |
| public class KthSmallestElementInArray { | |
| public static int find(int [] A, int k){ | |
| PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); | |
| for(int i=0;i<A.length;i++){ | |
| pq.offer(A[i]); | |
| } | |
| int n = –1; | |
| while(k>0){ | |
| n = pq.poll(); | |
| k—; | |
| } | |
| return n; | |
| } | |
| public static void main(String[] args) { | |
| int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 }; | |
| int k = 4; | |
| System.out.println("4th smallest element:" + find(A,4)); | |
| } | |
| } |
Output: 4th smallest element:10
Note: For kth largest element, implement priority queue for max-Heap.
Is it faster to use hte quickselect algorithm ?
It is also possible to just sort the input array in ascending order and pick the k-1th element.
That will take O(n) time. Idea here is to not sort the entire array. We can use priority queue or quick sort (i.e. partition only k times) and pivot will land in its correct position.
Why not just use Arrays.sort() and pick the k-1 th element?