第一轮
{2, 2, 3, 3}
全部通过

第二轮
{6, 7, 8, 9, 10}
全部通过

后面的测试数据用以下代码生成, SEED 和 DIM 控制生成不同的数据集

#define SEED  0
#define DIM   5
unsigned int arr[DIM];

void init()
{
    srand(SEED);
    for (unsigned int i=0; i<DIM; i++)
    {
        unsigned int a, b, c;
        a = rand() & 0x7ff;
        b = rand() & 0x7ff;
        c = rand() & 0x3ff;
        arr[i] = (a << 21) | (b << 10) | c;
    }
}

第四轮  
SEED = 0, DIM = 100;  正确答案应该是2164551488

joekings    53783761
其他人都过关

第五轮
SEED = 1, DIM = 1000;
三个程序全部过关

第六轮
SEED=2, DIM=10000;
braveheart2001    1.7s
WinWing        <1s
ITER        <1s

第七轮
SEED=3, DIM=100000;
braveheart2001    >>10S
WinWing        <1s
ITER        <1s
braveheart2001在这一轮被淘汰

第八轮
SEED=4, DIM=1000000;
ITER    1.2S
WinWing    1.2s

第九轮
SEED=5, DIM=10000000;
WinWing    13.8
ITER    13.2

再比下去也没什么意思了, 两个人都是用的快速排序, 速度应该是差不多的


这道题目一共只有4个人提交程序, 比较少了, 而且全部是先排序, 然后拿出中间那个数字
一个人是冒泡排序
三个人是快速排序
一旦使用排序,时间复杂度至少要有O(n*lgn)

事实上, 这道题有O(n)的算法, 我已经给了提示, 这道题和39次比较相似
下面的参考程序在上面最后一组数据的情况下也只要0.35s

unsigned int count2[65536];

unsigned int Mid(unsigned int array[], unsigned int n)
{
    unsigned int i, t, last, next, mask;
    unsigned int x = (n + 1) / 2;

    memset(count2, 0, sizeof(count2));
    for (i=0; i<n; i++)
        count2[(array[i] >> 16) & 0xffff] ++;
    
    t=0;
    for (i=65535; i>=0; i--)
    {
        last = t;
        t += count2[i];
        if (t >= x)
            break;
    }
    mask = i << 16;
    next = x - last;

    memset(count2,0,sizeof(count2));
    for (i=0; i<n; i++)
        if ((array[i] & 0xffff0000) == mask)
            count2[array[i] & 0xffff] ++;

    t=0;
    for (i=65535; i>=0; i--)
    {
        t += count2[i];
        if (t>=next)
            return (mask | i);
    }

    return 0;
}