2 yi zhangzhi yi_zhangzhi 于 2016.04.03 16:55 提问

求中位数的中位数那里好像有问题,我找不出来。求帮忙!感激! 10C

代码求第k小的数。编译过了,求中位数的中位数结果不对

 #include<stdio.h>
#include<stdlib.h>
void paixu(int *a,int p,int r)
{
    int b;
    for(int i=p;i<r;i++)
    {
        for(int j=r;j>i;j--)
        {
            if(a[j]>a[j-1])
            {
                b=a[j];
                a[j]=a[j-1];
                a[j-1]=b;
            }
        }
    }
}

void Swap(int *i,int *j)
{
    int b;
    b=*i;
    *i=*j;
    *j=b;
}


int Partition(int *a,int p,int r,int x)
{
    int i=p,j=r+1;
    while(true)
    {
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j)
            break;
        Swap(&a[i],&a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}

int Select(int *a,int p,int r,int k)
{
    int t;
    if(r-p<10)
    {
        paixu(a,p,r);
        return a[p+k-1];
    }
    for(int i=0;i<=(r-p-4)/5;i++)
    {
        paixu(a,p+5*i,p+5*i+4);
        Swap(&a[p+5*i+2],&a[p+i]);
    }
    printf("\n输出数组下标从p到p+(r-p-4)/5的元素:\n");
    for(int o=p;o<=p+(r-p-4)/5;o++)
    {
        printf("%3d",a[o]);
    }
    int x=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);
    printf("\n拟中位数:%d\n",x);
    i=Partition(a,p,r,x);
    int j=i-p+1;
    printf("输出p-r:\n");
    for(int q=p;q<=r;q++)
    {
        printf("%3d",a[q]);
    }
    if(k<=j)
        return Select(a,p,i,k);
    else
        return Select(a,i+1,r,k-j);
}

int main()
{
    int a[20]={11,12,14,10,13,9,8,5,4,6,1,2,3,7,16,17,18,19,20,15};
    int k,j;
    printf("k:");
    scanf("%d",&k);
    j=Select(a,0,19,k);
    printf("第k小的元素为:%d\n",j);
    return 0;
}

3个回答

caozhy
caozhy   Ds   Rxr 2016.04.03 18:36

int x=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);
这个是什么意思,你的select其实就是一个快速排序,然后找中间下标的那个。

http://www.cnblogs.com/RootJie/archive/2012/02/13/2349649.html

甚至你可以直接使用标准库的qsort

yi_zhangzhi
yi_zhangzhi int x=Select(a,p,p+(r-p-4)/5,(r-p+6)/10)是递归调用Select在中位数中再去找中位数,但是是错的
2 年多之前 回复
CSDNXIAON
CSDNXIAON   2016.04.06 17:02

求中位数的问题
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

CSDNXIAOD
CSDNXIAOD   2016.04.06 17:02

求中位数的问题
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
有序数组求中位数问题
1、有两个已排好序的数组A和B,长度均为n,找出这两个数组合并后的中间元素,要求时间代价为O(logn)。 2、假设两个有序数组长度不等,同样的求出中位数。 一:解析: 这个题目看起来非常简单。第一题的话: 假设数组长度为n, 那么我就把数组1和数组2直接合并,然后再直接找到中间元素。对于这样的方案,第一题和第二题就没有什么区别了。这样的话时间复杂度就是O(n)。通常在这样的情况下,那些要求比
减治算法之寻找两个递增序列的中位数
一、问题描述 寻找两个递增序列的中位数。 本算法中只能解决两个序列长度规模相等的问题,若两个序列长度规模不相等,则可以先做合并后再寻找中位数。 二、问题分析 分别计算序列A,B的中位数a,b 比较中位数a,b,会出现以下三种请款 (1)a = b,直接返回结果a (2)a (3)a > b,两个序列的中位数只能出现在[b,a),在序列中A中删除a之后的元素形成新序列A,在
利用分治法来求两个排序数组的中位数
有两个数组 ar1[] 和ar2[] 两个数组的长度都为n 求ar1[]和ar2[]的中位数 可以借鉴归并排序的思想 实质上就是将将两个已经排好序的数组 合并成一个数组 的过程只是在这个过程中添加了一个计算从小到大的次序的数 (count ) 当count =n 和n+1时记录下这两个数 然后在这两个数中间取平均值 就可以了 但是这个算法的复杂度是o(n)如果我们想达到log(n)的复杂度的
面试题之二叉搜索树的中位数
这个问题不算是很常见的问题,基本上在中文的论坛社区没有看到过,遇见这个是因为偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的,题目如下:Given a BST (Binary search Tree) how will you find median in that?   C
分治法-中位数
分治法-中位数 第一行: n,为x和y数组的元素个数 第二行: x数组的n个数,用空格分隔 第三行: y数组的n个数,用空格分隔
【leetcode4】用分治算法计算中位数问题
此题在leetcode中评级为hard,目的是在O(log(m+n))的时间复杂度情况下解决问题。用常规O(m+n)的算法很容易求得结果,但 显然不符合时间复杂度的要求。因此,这道题的解题分析主要还是利用分治算法去考虑,这也是本题的难点所在。 一、原题叙述 There are two sorted arrays nums1 and nums2 of size m and n respec
用最大堆和最小堆实现中位数查找
具体思路: 用一个最大堆存放比中位数小(或等于)的元素,用一个最小堆存放比中位数大(或等于)的元素。这里关键的方法是insert(),每当要插入一个元素时,根据判断条件将它插入最大堆或是最小堆,并更新最大堆和最小堆,使得最大堆和最小堆中元素的个数之差不超过1,这样中位数就是最大堆或最小堆的堆顶元素。当最大堆和最小堆中元素个数不同(个数相差为1)时,元素个数多的那个堆的堆顶元素即为中位数;如果两者
找中位数问题——分治法
题目:设A和B都是从小到大已经排好序的n个不等的整数构成的数组, 如果把A与B合并后的数组记作C,设计一个算法找出C的中位数。 解题思路: 思路一: 对将A和B合并数组成C,并且进行排序,然后直接输出中位数。 该算法的时间复杂度为:O(nlogn),空间复杂度为:O(n)。 思路二: 利用分治法。 假定A[0,……,n-1] 和 B[0,……,n-1] 是输入数组,令
算法,求1亿个数的中位数
http://bbs.csdn.net/topics/310150772 可以借鉴一下以下方法的: 有1亿个浮点数,请找出其中最大的10000个。提示:假设每个浮点数占4个字节,1亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。   ~~~~~~~~~~~~~   既然不可以一次读入内存, 那可以这么试试:   方法1: 读出100w个数据, 找出最大
算法----中位数算法的妙用(更新中)
部分背包问题: 一个窃贼去一家商店偷窃,有n件商品: 第i件物品值Vi元,重wi榜(vi, wi都是整数),他的背包最多只能装下W榜物品, 每件商品他可以选择一部分带走,而不是像0-1背包问题。问他最多能带走多贵的物品? 分析: 由于部分背包问题允许仅拿走物品的一部分,物件更像是金粉,可证明其具有贪心的性质。 算法1: 贪心 按照每榜的价值进行排序,然后由价值的大小依次往包里装,