线性时间选择算法java如何实现
时间: 2023-05-27 16:05:05 浏览: 65
线性时间选择算法是一种能够在O(n)时间复杂度内找到无序数组中第k小的元素的算法。下面是一种基于快速排序思想的Java实现:
```
public static int select(int[] arr, int k) {
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; // 如果k超出了数组范围,返回错误代码
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 选择第一个元素作为pivot
int i = left + 1, j = right;
while (i <= j) {
if (arr[i] < pivot) {
i++;
} else if (arr[j] >= pivot) {
j--;
} else {
swap(arr, i, j);
}
}
swap(arr, left, j); // 将pivot元素放到正确的位置
return j;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
```
该算法的核心是partition函数,它将数组分成两部分,左边的元素小于pivot,右边的元素大于等于pivot。然后根据pivot在数组中的位置与k的大小关系,决定继续在左边还是右边递归查找。每次递归都排除了一半的元素,因此时间复杂度为O(n)。