我有此代码用于在 O(n) 预期时间(O(n^2) 最坏情况下查找未排序数组的中位数)。我使用 long 是因为我希望能够持有 long 值。
public class Randomized {
long kthSmallestHelper(long arr[], long l, long r, long k)
{
if (k > 0 && k <= r - l + 1)
{
long pos = randomPartition(arr, l, r);
if (pos-l == k-1)
return arr[(int)pos];
if (pos - l > k - 1)
return kthSmallestHelper(arr, l, pos - 1, k);
return kthSmallestHelper(arr, pos + 1, r, k - pos + l - 1);
}
return Integer.MAX_VALUE;
}
void swap(long arr[], long i, long j)
{
long temp = arr[(int)i];
arr[(int)i] = arr[(int)j];
arr[(int)j] = temp;
}
long partition(long arr[], long l, long r)
{
long x = arr[(int)r], i = l;
for (long j = l; j <= r - 1; j++)
{
if (arr[(int)j] <= x)
{
swap(arr, i, j);
i++;
}
}
swap(arr, i, r);
return i;
}
long randomPartition(long arr[], long l, long r)
{
long n = r - l + 1;
long pivot = (long)(Math.random()) * (n - 1);
swap(arr, pivot + 1, r);
return partition(arr, l, r);
}
long kthSmallestRandom(long arr[], long k){
return kthSmallestHelper(arr, 0, arr.length - 1, k);
}
}
但是当我运行它时
long[] array = {12, 3, 5, 7, 4, 19, 26}; //median is 7
Randomized rand = new Randomized();
System.out.println(rand.kthSmallestRandom(array, (array.length + 1)/2));
这是不正确的(它返回 4)。
我的想法是使用这个版本的第 k 个最小数字来表示我想要 (length/2)th 最小的数字,即中位数。
我的想法或实施有什么问题?
月关宝盒
幕布斯6054654
相关分类