FindKthNumber.java

packagecom.thealgorithms.maths;

importjava.util.Collections;
importjava.util.PriorityQueue;
importjava.util.Random;

/**
 * Use a quicksort-based approach to identify the k-th largest or k-th max element within the provided array.
 */
publicfinalclassFindKthNumber {
privateFindKthNumber() {
 }

privatestaticfinalRandomRANDOM = newRandom();

publicstaticintfindKthMax(int[] array, intk) {
if (k <= 0 || k > array.length) {
thrownewIllegalArgumentException("k must be between 1 and the size of the array");
 }

// Convert k-th largest to index for QuickSelect
returnquickSelect(array, 0, array.length - 1, array.length - k);
 }

privatestaticintquickSelect(int[] array, intleft, intright, intkSmallest) {
if (left == right) {
returnarray[left];
 }

// Randomly select a pivot index
intpivotIndex = left + RANDOM.nextInt(right - left + 1);
pivotIndex = partition(array, left, right, pivotIndex);

if (kSmallest == pivotIndex) {
returnarray[kSmallest];
 } elseif (kSmallest < pivotIndex) {
returnquickSelect(array, left, pivotIndex - 1, kSmallest);
 } else {
returnquickSelect(array, pivotIndex + 1, right, kSmallest);
 }
 }

privatestaticintpartition(int[] array, intleft, intright, intpivotIndex) {
intpivotValue = array[pivotIndex];
// Move pivot to end
swap(array, pivotIndex, right);
intstoreIndex = left;

// Move all smaller elements to the left
for (inti = left; i < right; i++) {
if (array[i] < pivotValue) {
swap(array, storeIndex, i);
storeIndex++;
 }
 }

// Move pivot to its final place
swap(array, storeIndex, right);
returnstoreIndex;
 }

privatestaticvoidswap(int[] array, inti, intj) {
inttemp = array[i];
array[i] = array[j];
array[j] = temp;
 }

publicstaticintfindKthMaxUsingHeap(int[] array, intk) {
if (k <= 0 || k > array.length) {
thrownewIllegalArgumentException("k must be between 1 and the size of the array");
 }
PriorityQueue<Integer> maxHeap = newPriorityQueue<>(Collections.reverseOrder()); // using max-heap to store numbers.
for (intnum : array) {
maxHeap.add(num);
 }
while (k > 1) {
maxHeap.poll(); // removing max number from heap
k--;
 }
returnmaxHeap.peek();
 }
}