对于作业问题,我需要编写一个Java方法来使用quicksort风格的分区来查找数组中第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;
}
而且我已经写了基于Wikipedia's pseudocode这种方法:
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
我在做什么错?
难道我们假设你不能快速排序排序,然后就跳到指数?如果不是,输出数组以确保它实际上按正确的顺序。 – Thomas
不,排序是禁止的。 – Rubicon