Finding the kth smallest or kth largest element in an array.
Here’s an example of a Java program that finds the kth smallest element in an array using the QuickSelect algorithm:
import java.util.Arrays;
public class KthElementFinder {
public static int findKthSmallest(int[] arr, int k) {
if (arr == null || arr.length == 0 || k < 1 || k > arr.length) {
throw new IllegalArgumentException("Invalid input");
}
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int pivotIndex = partition(arr, left, right);
if (pivotIndex == k - 1) {
return arr[pivotIndex];
} else if (pivotIndex < k - 1) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
throw new IllegalArgumentException("Invalid input");
}
private static int partition(int[] arr, int left, int right) {
int pivotValue = arr[right];
int i = left;
for (int j = left; j < right; j++) {
if (arr[j] <= pivotValue) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, right);
return i;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = { 7, 10, 4, 3, 20, 15 };
int k = 3;
int kthSmallest = findKthSmallest(arr, k);
System.out.println("The kth smallest element is: " + kthSmallest);
}
}
In this program, the `findKthSmallest` method takes an array (`arr`) and an integer (`k`) as input and returns the kth smallest element in the array. It uses the QuickSelect algorithm, which is an efficient algorithm for finding the kth order statistic in an unordered list.
The `partition` method is used to rearrange the elements of the array such that all elements smaller than or equal to the pivot element appear before it, and all elements greater than it appear after it. The pivot element is chosen as the last element in the array.
The `main` method is a simple example that demonstrates how to use the `findKthSmallest` method. In this example, the array `{ 7, 10, 4, 3, 20, 15 }` is given, and we want to find the 3rd smallest element, which is 7. The program outputs: “The kth smallest element is: 7”.
You can modify the array and the value of `k` in the `main` method to test with different inputs and find the kth smallest element accordingly.