1

对于家庭作业问题，我需要编写一个 Java 方法来查找数组中第 k 个最小的数，使用快速排序样式的分区。我得到了 partition() 方法，我应该编写该方法来获得第 k 个最小的数字。

问题要求枢轴始终是数组范围中最右边的元素。

我得到了以下信息：

public int partition(int left, int right, long pivot) {
    int leftPtr = left - 1;
    int rightPtr = right + 1;
    while (true) {
        while (leftPtr < right && array[++leftPtr] < pivot); 
        while (rightPtr > left && array[--rightPtr] > pivot);

        if (leftPtr >= rightPtr)
            break;
        else
            swap(leftPtr, rightPtr);
    }
    return leftPtr;
}

我已经根据维基百科的伪代码编写了这个方法：

public int kthSmallest(int left, int right, int k){
    if(left >= right){
        return array[left];
    }

    int pivotNewIndex = partition(left, right, array[right]);

    int pivotDist = pivotNewIndex - left - 1;

    if(pivotDist == k){
        return array[pivotNewIndex];
    } else if(k < pivotNewIndex){
        return kthSmallest(k, left, pivotNewIndex - 1);
    } else{
        return kthSmallest(k - pivotDist, pivotNewIndex + 1, right);
    }
}

但是当我kthSmallest()用随机生成的整数数组调用时，大约有一半的时间它返回了错误的值。例如：

array: [45, 60, 24, 82, 87, 79, 16, 32, 59, 83, 20, 2, 1, 
         50, 11, 79, 72, 32, 0, 48, 69, 74, 22, 6, 96]
expected result when k=4: 11
actual result when k=4: 87

我究竟做错了什么？

4

3 回答 3

1

与维基百科伪代码相比，仔细查看您对 kthSmallest 的递归调用。k 索引参数相对于哪里？

于 2012-05-10T03:37:51.893 回答
1

您的递归调用的参数列表顺序错误。您正在查看的子数组中的位置应该是第三个参数，而不是第一个。

于 2012-05-10T03:46:16.750 回答
0

这是一个有效的解决方案（使用 Java 实现）：http ://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html

于 2013-05-24T20:33:29.210 回答