Leetcode:Median of Two Sorted Arrays再分析

题目我就不再贴了,大家可以自行往上翻一翻,这道题本质上就是找第k大的数字,关于这个问题,《数据结构与算法分析》一书中给出了几种不同的解法.
首先,是通过优先队列(堆)可以实现到O(N+klogN)算法,这个十分简单,我这里就不贴代码了,具体到题目求中位数,则复杂度为O(NlogN)
第二种,就是快速选择(quickselect),算法导论的第九章也介绍了这个内容,原理上与快速排序类似,但只要递归处理一边情况即可,quickselect的最坏情况与快速排序相同,同为O(N^2),但是其期望运行时间为O(N),最坏情况发生可能性极小,书后面还介绍了线性时间最坏时间算法,感兴趣的可以去看看。

最后,贴一段无序数组找第k小数字的代码(选取pivot不应该像下面那样挑第一个,下面的代码说实话挺烂的):

#include <stdio.h>
double qselect(int *A,int length);
int partition(int* A,int length);
double findMedianSortedArrays(int *A,int k,int length);
int main(void)
{
    int A[10]={1,6,8,7,1,2,3,5,18,9};
    printf("%lf",qselect(A,10));
    return 0;
}

double qselect(int *A,int length)
{
    if(length==1)
        return A[length];
    if(length%2!=0)
        return findMedianSortedArrays(A,length/2+1,length);
    else
        return (findMedianSortedArrays(A,length/2,length)+findMedianSortedArrays(A,length/2+1,length))/2;
}

int partition(int* A,int length)
{
    int pivot=A[0];
    int i=0,j=length-1;
    while(i<j)
    {
        while(A[j]>=pivot&&i<j)
            j--;
        while(A[i]<=pivot&&i<j)
            i++;
        if(i<j)
        {
            int temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
    }
    A[0]=A[i];
    A[i]=pivot;
    return i;
}

double findMedianSortedArrays(int *A,int k,int length)
{
    if(length==1)
        return A[length];
    int part=partition(A,length);
    if(part==k-1)
        return A[part];
    if(part<k-1)
        return findMedianSortedArrays(A+part+1,k-part-1,length-part-1);
    else
        return findMedianSortedArrays(A,k,part+1);
}   

 

发表评论

This site uses Akismet to reduce spam. Learn how your comment data is processed.