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

我有此代码用于在 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 最小的数字,即中位数。


我的想法或实施有什么问题?


哔哔one
浏览 187回答 2
2回答

月关宝盒

kthSmallestHelper此行中的函数有一个小错误:if&nbsp;(pos-l&nbsp;==&nbsp;k-1)&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;arr[(int)pos];返回使用了错误的索引。尝试pos-l+1代替pos(并将其转换为int)。这将返回第 k 个项目,该项目刚刚排序到数组中的正确位置。

幕布斯6054654

我不在一个可以运行它的位置,但在这一点上似乎有很多问题。在 Java 中,当您将数组传递给函数时,只会传递数组的副本,因此您所做的任何交换都不会更改该方法之外的数组。看起来你的分区也关闭了。而不是传入分区,你只是传入左右边界,看起来你的分区方法只将东西发送到分区的左侧。这段代码应该被更多地注释,这样我们就可以知道你在每个点上要做什么。此外,由于您将事物交换为排序顺序,因此它看起来像 O(nlogn),因为您无法在线性时间内排序。为什么不能使用 k == 0 作为第 k 个最小的助手?
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Java