位图算法－找中值

Blog许久没有更新了，原因是没有素材。:) 今天借老杨的树《》开朵小花吧:p

本人在一个工程任务中,需要完成“在9个整数中，找到中值”。
比如：1,3,5,7,9,2,4,6,8 的中值是5。

看似非常简单的一个小问题，但由于每秒钟需要调用大约10万多
次，因此我需要一个快速算法，不考虑空间浪费，只要求比较语
句尽可能的少。

我这里用是位图算法，最差情况需要线性扫描数组2遍，空间复杂度为2O。当数据分布过分的稀疏的话，可能复杂度为nO。:(  不过，总体来说比O²的算法要快一些吧）下面是随手写的一段代码，只是为了演示算法，写的不够规范，有很多地方可以优化，见谅见谅。:P

//
// Sample for vector arithmetic
// Write by spark
// 2006-04-02
//

#include 

int arr[] = {1,3,5,7,9,2,4,6,8};            

#define MAX_NUM             (9)             //arr[]中的最大数
#define MIN_NUM             (1)             //arr[]中的最小数
                                                  //为了构建位图使用

#define ARR_MAX_INDEX       (sizeof(arr)/sizeof(arr[0]))   //arr[]中元素个数 
#define VEC_MAX_INDEX       ((MAX_NUM)+1)                  //创建0~MAX_NUM的位图，这里可以优化，改为创
                                                                   //建MIN_NUM~MAX_NUM的位图,以节省空间。


int main(int argc, char *argv[])
{
    int vector_flag[VEC_MAX_INDEX] = {0};      //这里很浪费空间。:) 
                                               //对空间有限制的话可以把32个flag压缩到一个int里
    int i, j, k;
    int middle_index;

    // set flag
    for (i=0; i<ARR_MAX_INDEX; i++)
    {
        vector_flag[arr[i]] = 1;
    }
   
    // search middle
    middle_index = (ARR_MAX_INDEX+1) / 2;       //注:这里假设arr[]中没有重复的值，否则要改
                                                       //变middle_index的算法。
    i=MIN_NUM-1; j=0;
    while(j<middle_index && i<VEC_MAX_INDEX)
    {
        i++;
        if (vector_flag[i]==1) 
        {
            j++;
        }
    }

    // print result
    printf("middle number is : %d", i);

    return 0;
}

欢迎拍砖，欢迎去老杨的家拍其他人的砖:p
-------------
乾坤一笑 写于2006年04月02日  转载请标明出处和原文链接 


--------------------next---------------------

嘿嘿，比如下面这组数，用的算法应该怎么算？
1,2,3,4,9
你得出的中值是3还是4啊？:p

不知道最值，添加cur_max,cur_min两个变量，在设置flag的那轮扫描中就可以同时把最值给求出来。

int cur_max, cur_min; 
cur_max = cur_min = arr[0]; 
for (i=0; i<ARR_MAX_INDEX; i++) 
{ 
    if (arr[i]>cur_max) 
        cur_max = arr[i]; 
    if (arr[i])<cur_min) 
        cur_min = arr[i]; 
    vector_flag[arr[i]] = 1; 
} 
//for循环后，cur_max为数组最大值，cur_min为最小值 

--------------------next---------------------