求一个无序数组的中位数。

问题描述

求一个无序数组的中位数。 如：{2,5,4,9,3,6,8,7,1}的中位数为5，{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。

要求：不能使用排序，时间复杂度尽可能低。

提示：考虑堆或者快排思想解决

方法1：堆

思路1： 分析：将数据平均分配到最大堆和最小堆中，并且保证最小堆中的数据存放的数据都比最大堆中是数据大，那么此时最小堆堆顶的元素一定是中位数。 那么如何保证最小堆中的元素，都比大堆中的元素大。

(1)遍历数组，将第i个数插入堆中，i为奇数时，插入最小堆，i为偶数时插入最大堆。(最大堆的插入的数据比较大) (2)每次插入时，将最大堆和最小堆的堆顶交换

void GetMid(int arr[],int size) { priority_queue<int> max_heap; priority_queue< int, vector<int>, greater<int> > min_heap; for (int i = 0; i < size; ++i) { //i是从0开始的，所以max存放的数据比较多 if ((i & 1) == 1) min_heap.push(arr[i]); else max_heap.push(arr[i]); //每次交换最大堆和最小堆中的数据，保证最小堆中的数据大于最大堆中 if (!min_heap.empty() && !max_heap.empty()) { int temp = min_heap.top(); min_heap.pop(); max_heap.push(temp); temp = max_heap.top(); max_heap.pop(); min_heap.push(temp); } } if ((size & 1)== 0)//偶数 cout << "中位数：" << max_heap.top() << " " << min_heap.top() << endl; else cout << "中位数：" << max_heap.top() << endl; }

思路2： (1)将前(n+1)/2个元素调整为一个小顶堆，

(2)对后续的每一个元素，和堆顶比较，如果小于等于堆顶，丢弃之，取下一个元素。 如果大于堆顶，用该元素取代堆顶，调整堆，取下一元素。重复这个步骤

(3) 当遍历完所有元素之后，堆顶即是中位数。

void GetMid2(int arr[],int size) { priority_queue< int, vector<int>, greater<int> > min_heap; int count = (size + 1) >> 1; //存放count个数，比如5个元素，存放3个 for (int i = 0; i <= count; ++i) min_heap.push(arr[i]); for (int i = count + 1; i < size; ++i) { int temp = min_heap.top(); if (arr[i] > temp) { min_heap.pop(); min_heap.push(arr[i]); } } if ((size & 1) == 1)//奇数 { min_heap.pop(); cout << "中位数：" << min_heap.top() << endl; } else { int tmp = min_heap.top(); min_heap.pop(); cout << "中位数：" << tmp <<" "<< min_heap.top() << endl; } }

方法2、快排

快速排序之所以得名”快排”,绝非浪得虚名！因为快排就是一种分治排序法！

同样，找中位数也可以用快排分治的思想。具体如下：

任意挑一个元素，以改元素为支点，划分集合为两部分，如果左侧集合长度恰为 (n-1)/2，那么支点恰为中位数。如果左侧长度<(n-1)/2, 那么中位点在右侧，反之，中位数在左侧。 进入相应的一侧继续寻找中位点。

这种方法很快，但是在最坏的情况下时间复杂度为O(N^2), 不过平均时间复杂度好像是O(N)。

//快排方法，分治思想 //挖坑法 int PartSort(int arr[], int left,int right) { int key = arr[right]; while (left < right) { //key右边，先从左找比key值大 while (left < right && arr[left] <= key) ++left; if (left < right) { arr[right] = arr[left]; --right; } //从右找比key小 while (left < right && arr[right] >= key) --right; if (left < right) { arr[left] = arr[right]; ++left; } } arr[left] = key; return left; } void GetMid3(int arr[],int size) { int left = 0; int right = size - 1; int mid = size / 2; int div = PartSort(arr, left, right); while (div != mid) { if (div < mid)//右半区间 { div = PartSort(arr, div + 1, right); } else { div = PartSort(arr, left, div - 1); } } cout << "中位数" << arr[div] << endl; }