用选择问题算法实现法在无序序列中找到第k小的数用java代码
时间: 2024-09-27 07:07:07 浏览: 19
在无序序列中找到第k小的数,可以使用一种叫做“快速选择”(QuickSelect)的选择算法,它是快速排序算法的一个变种。快速选择通过随机化的方式避免最坏情况的发生,平均时间复杂度为O(n)。以下是使用Java实现的简单版本:
```java
import java.util.Random;
public class QuickSelectKthLargest {
public static int quickselect(int[] nums, int k) {
if (nums == null || nums.length == 0 || k < 1 || k > nums.length) {
throw new IllegalArgumentException("Invalid input");
}
return quickselectHelper(nums, 0, nums.length - 1, k);
}
private static int partition(int[] nums, int left, int right) {
int pivotIndex = randomPartitionIndex(left, right);
swap(nums, pivotIndex, right); // Pivot is always the last element in this case
int pivotValue = nums[right];
int i = left;
for (int j = left; j < right; j++) {
if (nums[j] <= pivotValue) {
swap(nums, i++, j);
}
}
swap(nums, i, right);
return i;
}
private static int randomPartitionIndex(int left, int right) {
Random rand = new Random();
return rand.nextInt(right - left + 1) + left;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private static int quickselectHelper(int[] nums, int left, int right, int k) {
if (left == right) { // Base case: only one element
return nums[left];
}
int pivotIndex = partition(nums, left, right);
if (k == pivotIndex) {
return nums[k]; // Found the k-th largest
} else if (k < pivotIndex) {
// Recurse on the left subarray
return quickselectHelper(nums, left, pivotIndex - 1, k);
} else {
// Recurse on the right subarray
return quickselectHelper(nums, pivotIndex + 1, right, k);
}
}
public static void main(String[] args) {
int[] nums = {3, 6, 8, 10, 1, 2, 1};
int k = 3;
System.out.println("The " + k + "-th smallest number is: " + quickselect(nums, k));
}
}
```
这个代码首先检查输入是否有效,然后通过递归实现快速选择过程,直到找到第k小的元素。