使用快速排序的变体的第k个最小数
用户名
我有以下分区方法和kthsmallest方法（快速排序的变化），在某些情况下可以使用，但在某些情况下可以提供32767的值。
void swap(int* a, int* b){
int temp = *b;
*b = *a;
*a = temp;
}
int partition(int* arr, int l, int r){
int pivot = arr[r];
int i = l, j=0;
for(j=l; j<=r-1; j++){
if(arr[j] <= pivot){
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[j]);
return i;
}
并且第k个最小的函数如下：-
int kthsmallest(int* arr, int low, int high, int k){
/* low = 0 and high = #elements - 1 */
/* k is in between 1 to high + 1 */
if (k>0 & k<=high-low+1) {
// pos is partitioning index, arr[p] is now at right place
int pos = partition(arr, low, high);
// Separately sort elements before / partition and after partition
if(pos-low == k-1){
return arr[pos];
}
//if position returned is greater than k, recurse left subarray
else if(pos-low > k-1){
return kthsmallest(arr, low, pos-1, k);
}
return kthsmallest(arr, pos+1, high, k-(pos+1));
}
}
但是当我在kthsmallest函数中更改最后一个调用时它即有效
改变： return kthsmallest(arr, pos+1, high, k-(pos+1));
至： return kthsmallest(arr, pos+1, high, k-(pos+1)+low);
我想了解为什么我需要对k-（pos + 1）添加低。因为在我看来，当我们在右边有递归输入的子数组时，大数组中的第k个最小数字归结为k-最后一个分区元素-1，即k-（pos + 1）。
杜巴菲克
您需low要这样做，因为当您递归地从一个新数组开始时，low将成为的参考pos。因此，新k值将从low到进行计算pos。
也许一个例子会更加明确。
让我们找到此数组的第9个最小元素： 
现在我们进行分区，因此我们得到： 
从pos向左我们已经得到了数组，这就是3个最小的元素中最小的元素。现在，我们将从开始的子数组pos+1。我们需要得到第六个最小的元素：
我们对该子数组进行分区： 
请记住，我们正在尝试寻找第六个最小元素的子数组。在这种情况下，我们(pos - low + 1)在子数组中分离了最小的元素。因此，我们的新方法k将是：
我们做一个新的分区：
现在我们超过了最后一个子数组的第4个最小元素，因此我们修剪了最后一部分：
我们再次进行分区：
我们得到： 
所以我们的电话是17。
希望能帮助到你。
PD：正如David C. Rankin在评论中所说，您可能应该更改&为&&。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
使用快速排序的变体的第k个最小数
- 2
快速选择算法以找到第k个最小数的实现
- 3
快速选择算法以找到第k个最小数的实现
- 4
第k个最小数字
- 5
求和等于m的第k个最小数
- 6
部分排序以找到第k个最大/最小元素
- 7
部分排序以找到第k个最大/最小元素
- 8
检查x是否大于最小堆中的第k个最小数
- 9
使用分区的数组中第K个最小元素
- 10
两个排序数组的并集中的第k个最小元素
- 11
两个排序数组的并集中的第k个最小元素
- 12
从两个排序的数组中找到第k个最小的元素
- 13
如何在不对列表进行排序的情况下找到列表的第k个最小元素？
- 14
返回第k个最小元素的函数
- 15
在Python中大小为N的未排序列表中获取k个最小数字的最快方法？
- 16
在O（log n）中找到第k个最小元素
- 17
Java TreeMap获得第K个最小键
- 18
递归获得数组中第k个最小的元素
- 19
最大堆查找第 k 个最小元素
- 20
计算使用冒泡排序算法将第一个k最小元素排序的交换次数
- 21
最小堆中大于或等于x的第K个最小元素
- 22
有k个节点的Dijkstra变体？
- 23
如何在Scala中获取优先级队列的第k个最小元素？
- 24
通过随机枢轴法找到第K个最小元素。一些奇怪的错误
- 25
如何使用MERGE SORT对K个排序的数组进行排序
- 26
如何在多维数组中找到k个最小数字的索引？
- 27
如何在多维数组中找到k个最小数字的索引？
- 28
查找数组中k个最小数字的索引的算法
- 29
用最小堆对k排序的数组排序
我来说两句