我正在尝试使用quickselect算法找到数组中的第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
在这些测试用例中,random pivot给出了任何一个数组元素作为输出。
任何可能是bug的提示都将非常有用。
根据@nico的建议,我只需要将pivot元素与最后一个元素交换。
下面是完整的工作片段,
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;
}
}
}
我知道以前有人问过这个问题,但这个问题是关于我的具体代码。我试图做一个psuedo-QuickSelect算法,将k与排序矩阵子区间的中点进行比较。 我一直收到一个超时错误。 以下是矩阵: 下面是我的代码: 我将元组传递给,其中包含区间的endpoint的。因此,如果我想搜索整个矩阵,我会传递和。将查看子区间,根据endpoint的行号确定中点,计算小于中点的元素数量,将其与进行比较。如果小于小于
如果您有长度的排序数组,请查找其中最小的元素。这里有一些潜在的解决方案,有些涉及最小堆或二进制搜索,但我想知道使用QuickSelect的时间复杂度是多少。如果我们简单地将每个数组连接在一起,并在组合数组上使用quickselect。 Quickselect在一般情况下以线性时间运行,但是数组的组合确实会扩展搜索空间,但它比使用合并策略更有效,因为如果选择了好的枢轴,Quickselect必然允许
为了好玩/Java实践,我做了以下问题: 编写一个方法,该方法将整数的优先级队列作为输入,并输出最小整数。该方法不应更改传入的优先级队列的内部状态。您只能使用一个队列或堆栈作为额外数据。不允许使用其他数据结构<代码>k为1索引(表示最小值)。 获取元素很简单:只需删除次,因为它是优先级队列。我想我可以弹出,将元素放在堆栈上进行存储,然后在完成后将它们添加回队列。不过这不起作用,因为元素在优先级队列
这是一个面试问题。 在具有排序行和列的矩阵中找到Kth最小元素。 Kth最小元素是中的一个,例如,这是否正确?
我最近接受了一家社交媒体公司的面试,在那里我被问到了以下问题。 有k个长度为m的未排序数组。目标是在给定a 我提出了两个可能的解决方案: null 对于使用quickselect查找第b个最小元素的第一步,平均时间总共从O(km)到O(km*log(m))。第二步时间复杂度为O(km)。最后一步是在C中的第a和第b个最小元素之间寻找元素,取O((b-a)log(kb))。因此,total在时间上需
我目前正在研究选择算法,即中位数。 我遇到了下面两个句子: 在计算机科学中,选择算法是寻找列表或数组中第k个最小数的算法; 在计算机科学中,中位数是一种近似(中位数)选择算法,经常用于为精确选择算法(主要是quickselect)提供良好的中枢,该算法选择最初未排序数组的第k个最大元素。 第k个最小/最大元素是什么意思?为了使问题更具体一点,考虑以下(未排序)数组: 例如,第五小的元素是什么?第五