前段时间面试遇到一个小题 把我难住了，题目是数组中有N个正整数，数组存储是无序的，求数组的中位数。当时没想出好的办法 ，在离开后，到了地铁上，我想到一个办法。可以快速解决问题。之前没有研究过这个问题，这个方法全凭我用脑子想出来的。希望大家能提出更好的办法或者建议。
假如数组中的每个正整数是四字节类型的，则数组的大小范围是 0x 00 00 00 00 到 0x 7F FF FF FF。我们一般最先想到的办法 就是采用排序的方法将数组排序，排序后位于数组 N / 2 位置的数即中位数。（这里我们为了简便，不考虑N是奇数还是偶数，如果是奇数，那就是N/2位置的数，如果是偶数，则是N/2 和 N/2+1位置上的两个数的平均值。）采用排序的办法 ，时间复杂度最少为O(NlogN)，太慢。
我想到的方法时间复杂度是O(N)。思路是这样的：
（1）建立一个256的统计数组（记为hist），全部置0，统计原始数组（记为array）元素最高字节的出现的次数；
（2）然后对统计数组进行遍历，找到中值所处的位置，记为mid，则hist[0]到hist[mid-1]的总和记为num_left, hist[mid+1]到hist[255]的总和记为num_right，则
num_left + num_right + hist[mid] = N，并且 num_left <= N/2 和 num_right <= N/2
（3）对原始数组中最高字节为mid值的所有元素的次高字节进行统计，再找出新的中值，将中值左边的总数加到num_left中，将中值d右边的总数加到num_right，以此类推，直到找到最低字节。
下面看源代码，源代码中焉整数的范围只是0x 00 00 到 0x FF FF ，主要是为了简单阐述我的思路。
/*问题：求正整数数组中的中值。正整数的范围是0 到 0xFF FF思路： （1）先对最高字节通过256的直方图求中值，并统计出中值左右两边分别的数量 （2）求（1）求得的中值，再只对数组中所有最高字节等于中值的元素，求次高元素的中值 （3）以此类推 */#include "stdafx.h"#include#include #include #include //数组的大小#define N 10001//打印数组内容void print(int* arr, int len);//求中值int GetMidNum(int* arr, int len);//冒泡排序void sort_bubble(int* arr, int len);int _tmain(int argc, _TCHAR* argv[]){ int *arr = new int[N]; //产生随机数 srand((unsigned int)time(NULL));//initialize random seed; for (int i = 0; i < N; i++) { int a = rand() % 256; int b = rand() % 256; arr[i] = a + (b << 8); } //print(arr, N); //求中值 clock_t t1 = clock(); int midNum = GetMidNum(arr, N); clock_t t2 = clock(); printf("求中值的结果：%x 时间：%d\n", midNum, (t2 - t1) ); //通过排序，求中值，检测上述方法的结果是否正确 clock_t t3 = clock(); sort_bubble(arr, N); clock_t t4 = clock(); printf("排序得中值为：%x 时间：%d\n", arr[N / 2], (t4 - t3) ); //print(arr, N); delete []arr; system("pause\n"); return 0;}void print(int* arr, int len){ printf("\nprint start\n"); for (int i = 0; i < len; i++) { printf("%4x ", arr[i]); if (i % 10 == 9) { printf("\n"); } } printf("\nprint end \n");}int GetMidNum(int* arr, int len){ const int HIST_NUM = 256; int *hist = new int[HIST_NUM]; memset(hist, 0, sizeof(int) * HIST_NUM); //求中值 int midNum = 0; int num_left = 0; int num_right = 0; //统计最高位字节， for (int i = 0; i < len; i++) { hist[ arr[i] >> 8 ]++; } //累积直方图 for (int i = 1; i < HIST_NUM; i++) { hist[i] += hist[i - 1]; } //求高位中值 for (int i = 0; i < HIST_NUM; i++) { if (hist[i] - 1 >= len / 2) { midNum = i; num_left = hist[i - 1]; num_right = len - hist[i]; break; } } memset(hist, 0, sizeof(int) * HIST_NUM); //统计最低位字节， for (int i = 0; i < len; i++) { //printf("%2x %2x \n", arr[i], arr[i] >> 8); if ( (arr[i] >> 8) == midNum) { hist[ (arr[i] & 0xFF) ]++; } } int midNum2 = 0; for (int i = 0; i < HIST_NUM; i++) { num_left += hist[i]; if (num_left - 1 >= len / 2 ) { midNum2 = i; break; } } midNum = midNum << 8; midNum += midNum2; delete []hist; return midNum;}void sort_bubble(int* arr, int len){ for (int i = 0; i < len; i++) { int flag = i; for (int j = flag + 1; j < len; j++) { if (arr[j] < arr[flag]) { flag = j; } } if ( i != flag ) { int temp = arr[i]; arr[i] = arr[flag]; arr[flag]= temp; } }}