如何实现随机 O(n) 算法来查找 Java 中未排序数组的中位数？

Question

我有这段代码用于在 O(n) 预期时间、O(n^2) 最坏情况下查找未排序数组的中值。我使用 longs 是因为我希望能够保存 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));

不正确（returns 4）。

我的想法是使用这个版本的第 k 个最小的数字来表示我想要第 (length/2) 个最小的，也就是中位数。

我的想法或实现有什么问题？

Answer 1

您的 kthSmallestHelper 函数在这一行中有一个小错误：

if (pos-l == k-1) 
    return arr[(int)pos];

return 使用了错误的索引。尝试 pos-l+1 而不是 pos（并将其转换为 int）。这 return 是第 k 个项目，它刚刚被排序到数组中的正确位置。

Answer 2

我不在运行它的位置，但在这一点上似乎有很多错误。

在 Java 中，当您将数组传递给函数时，只会传递数组的副本，因此您将进行的任何交换都不会在该方法之外更改数组。看起来您的分区也已关闭。您没有传入分区，而是传入了左右边界，看起来您的分区方法只将内容发送到分区的左侧。

这段代码应该多加注释，这样我们才能知道您在每一点上要做什么。 ALso 它看起来因为你正在将事物交换成排序顺序它会是 O(nlogn) 因为你不能在线性时间内排序。为什么不能对第 k 个最小的助手使用 k == 0？

Answer 3

我不知道为什么，只是将所有 longs 更改为 ints 修复了它。它现在按预期工作。

如何实现随机 O(n) 算法来查找 Java 中未排序数组的中位数？

How to implement randomized O(n) algorithm for finding median of unsorted array in Java?

java

sorting

algorithm

median