题目二:次序选择问题 对于给定的n个元素的数组a[1..n],要求从中找出第k小的元素。 【输入样例】 a={20, 43, 32, 67 ,48, 89, 36, 47, 15} k=3 【输出样例】 32 2.数据输入:个人设定,由键盘输入。用分治法用java实现
时间: 2024-06-03 18:10:31 浏览: 10
可以使用快速排序中的partition函数来实现次序选择问题,思路如下:
1. 首先选择一个pivot,将数组分成小于pivot和大于等于pivot两部分。
2. 如果小于pivot的元素个数大于等于k,则在小于pivot的部分递归查找第k小的元素。
3. 如果小于pivot的元素个数小于k,则在大于等于pivot的部分递归查找第k-smallerNum小的元素。
代码如下:
private static int selectKthSmallest(int[] arr, int k) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int pivotIndex = partition(arr, left, right);
int smallerNum = pivotIndex - left + 1;
if (k == smallerNum) {
return arr[pivotIndex];
} else if (k < smallerNum) {
right = pivotIndex - 1;
} else {
left = pivotIndex + 1;
k -= smallerNum;
}
}
return -1; // 如果没找到返回-1或抛出异常
}
private static int partition(int[] arr, int left, int right) {
int pivotIndex = choosePivotIndex(arr, left, right); // 选择pivot可以使用随机数、中位数等方法
int pivotVal = arr[pivotIndex];
swap(arr, pivotIndex, right);
int i = left, j = right - 1;
while (i <= j) {
if (arr[i] < pivotVal) {
i++;
} else if (arr[j] >= pivotVal) {
j--;
} else {
swap(arr, i++, j--);
}
}
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;
}
注意选择pivot的方法也会影响算法效率,可以使用随机数或者取中位数等方式进行优化。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)