关于一个在一组无序数中查找第k大的数算法 - 编程论坛

#2

hahayezhe2010-03-28 15:48

学习了！

#3

玩出来的代码2010-03-28 21:30

贴个代码，有局限性的，只能处理整形数,O(n)的时间不过如果数据太大空间会增大。应该还有更好的方法。

程序代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    int a[6]={2,4,67,8,3,5};
    int i,max=0,count=0;
    int k;
    scanf("%d",&k);
    for(i=0;i<6;i++)
    {
        max=max>a[i]?max:a[i];
    }
    int *p=(int*)malloc(sizeof(int)*max+1);
    memset(p,0,sizeof(int)*max+1);
    for(i=0;i<6;i++)
    {
        p[a[i]]=a[i];
    }
    for(i=max;i>0;i--)
    {
        if(p[i]!=0)
        {
            count++;
            if(count==k)
            {
                break;
            }
        }
    }
    printf("%d",p[i]);
    return 0;
}

[ 本帖最后由玩出来的代码于 2010-3-28 21:39 编辑 ]

#4

asdjc2010-03-29 20:44

三楼的朋友，你的代码中时间复杂度是o（m），m为数组中最大数。那样效果就不好了吧。

#5

liruikai2012-10-10 10:42

学习了，谢谢

#6

liruikai2012-10-10 10:58

一楼和三楼的思想都很high，，，汲取所长，