java - 使用带有随机枢轴的快速选择的第 K 个最小元素
问题描述
我正在尝试使用快速选择算法在数组中找到第 k 个最小的。但是,当我尝试随机选择枢轴时,输出也是随机的。
以下是我的方法实现,
static int findKthMin(int[]arr, int n, int k) {
int l=0 , r=n-1;
Random random = new Random();
while(true) {
int x = random.nextInt(r+1-l) + l; // When using x = r (works correctly)
int pivot = arr[x];
int idx = l;
for(int i=l;i<=r;i++) {
if(arr[i] < pivot) {
int temp = arr[idx];
arr[idx] = arr[i];
arr[i] = temp;
idx++;
}
}
arr[x] = arr[idx];
arr[idx] = pivot;
if(idx == k-1) return pivot;
if(idx > k-1) {
r = idx-1;
} else {
l = idx;
}
}
}
这里,n
是数组的大小,k
是要找到的第 k 个最小元素。
当我使用x=r
.
我的猜测是情况有问题
for(int i=l;i<=r;i++) {
if(arr[i] < pivot) {
int temp = arr[idx];
arr[idx] = arr[i];
arr[i] = temp;
idx++;
}
}
但我无法弄清楚出了什么问题以及如何解决它。我花了几个小时调试它并更改代码,但可以找出问题所在。
这是我正在尝试的测试用例,
6 // n
7 10 4 3 20 15 //arr
3 // k
和,
5 // n
7 10 4 20 15 // arr
4 // k
使用这些测试用例,随机枢轴将任何数组元素作为输出。
任何可能是错误的提示都将非常有帮助。
解决方案
在@Nico 的建议之后,我只需要将枢轴元素与最后一个交换。
以下是完整的工作片段,
static int findKthMin(int[]arr, int n, int k) {
int l=0 , r=n-1;
Random random = new Random();
while(true) {
int x = random.nextInt(r+1-l) + l; // When using x = r (works correctly)
//Swap random pivot with the last index element
int temp = arr[x];
arr[x] = arr[r];
arr[r] = temp;
int pivot = arr[r];
int idx = l;
for(int i=l;i<=r;i++) {
if(arr[i] < pivot) {
temp = arr[idx];
arr[idx] = arr[i];
arr[i] = temp;
idx++;
}
}
arr[r] = arr[idx];
arr[idx] = pivot;
if(idx == k-1) return pivot;
if(idx > k-1) {
r = idx-1;
} else {
l = idx;
}
}
}
推荐阅读
- sql-server - SQL FUNCTION LIKE SEARCH ISSUE
- javascript - 使用 express 和 react 应用程序出现“No 'Access-Control-Allow-Origin' header”的问题
- spring - 异常:org.hibernate.LazyInitializationException:未能延迟初始化角色集合
- javascript - 在 CSS 中定义自适应边界线
- powershell - 如何从powershell中的文本表中删除第n列?
- angular - 在 Angular 中创建动态菜单
- c - 是否可以利用以下代码?
- vue.js - 将数据传递给 VueJS 中的另一个组件
- vb.net - 从服务器更新 VSTO 加载项
- maven - 在将构建的 jar 发布到 github 时,是否有使用 github 操作上传的功能?