O(n)时间求最接近中位数的k个数

题目：

    给出一个O(n)时间的算法，在给定一个有n个不同数字的集合S以及一个正整数k<=n后，它能确定出S中最接近其中位数的k个数

思考：

    step1：求出数组的中位数的值O(n)

    step2：计算数组每个数与中位数差的绝对值，存于另一个数组B中O(n)

    step3：求出数组B中第k小的数ret O(n)

    step4：计算数组S中与中位数的差的绝对值小于ret的数并输出O(n)

    其中，step4也可以通过划分的方法找出数组S中与ret差的绝对值小于ret的数

ps：上面思路来自：http://blog.csdn.net/mishifangxiangdefeng/article/details/7689900

        代码实现如下所示。

#include <iostream>
#include <ctime>

using namespace std;

#define MAXNUM 100

/************求中位数***************/
void Swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

//随机划分
int PartitionRandom(int a[], int first, int last)
{
    int priot = first + rand() % (last - first + 1);
    Swap(&a[first], &a[priot]);
    int key = a[first];

    while(first < last)
    {
        while(first < last && a[last] >= key)
        {
            last--;
        }
        Swap(&a[first], &a[last]);

        while(first < last && a[first] <= key)
        {
            first++;
        }
        Swap(&a[first], &a[last]);
    }
    return first;
}

int Select(int a[], int first, int last , int i)
{
    if(first == last)
    {
        return a[first];
    }
    int priot = PartitionRandom(a, first, last);
    int k = priot - first + 1;
    if(k == i)
    {
        return a[priot];
    }
    if(k > i)
    {
        return Select(a, first, priot - 1, i);
    }
    else//k < i
    {
        return Select(a, priot + 1, last, i - k);
    }
}


/******寻找最接近中位数的k个数*******/
//length：数组的长度
void FindKNums(int a[], int length, int k)
{
    if(k > length)
    {
        return;
    }

    //step1:求出数组的中位数的值O(n)
    int mid = Select(a, 0, length - 1, length / 2);

    cout << "mid = " << mid << endl;

    //step2:计算数组每个数与中位数差的绝对值，存于另一个数组B中O(n)
    int *b = (int *)malloc(sizeof(int) * length);
    if(b == NULL)
    {
        return;
    }

    for(int i = 0; i < length; i++)
    {
        b[i] = (int)fabs(double(a[i] - mid));
    }

    //step3:求出数组B中第k小的数ret O(n)
    int ret = Select(b, 0, length - 1, k);

    cout << "ret = " << ret << endl;

    //step4:计算数组S中与中位数的差的绝对值小于ret的数并输出O(n)
    for(int i = 0; i < length; i++)
    {
        int tmp = (int)fabs(double(a[i] - mid));
        if(tmp <= ret)
        {
            cout << a[i] << " ";
        }
    }
    cout << endl;




}
int main(int argc, char* argv[])
{
    int a[MAXNUM];
    int length;
    int k;
    cout << "输入数组中元素的个数:";
    cin >> length;
    cout << "输入查找最接近中位数的个数:";
    cin >> k;
    //随机产生数组元素
    srand((unsigned)time(NULL));
    for(int i = 0; i < length; i++)
    {
        a[i] = rand() % 100 - 1;
    }
    cout << "产生的元素为：" << endl;
    for(int i = 0; i < length; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    FindKNums(a, length, k);
    return 0;
}

   





            

                                                    梦醒潇湘love
                                            2013年4月17日 19:05