线性时间第k选择Java代码
时间: 2023-05-19 22:02:27 浏览: 69
以下是一个基于快速选择算法的线性时间第k选择Java代码:
public static int kthSmallest(int[] arr, int k) {
if (arr == null || arr.length < k) {
return -1;
}
int left = 0, 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) {
right = pivotIndex - 1;
} else {
left = pivotIndex + 1;
}
}
return -1;
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
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;
}
请注意,这只是一个示例代码,实际上可能还需要进行一些优化和错误处理。