寻找中位数的快速算法

发表于 | 分类于 | 阅读次数：
本文字数： 1.6k | 阅读时长 ≈ 4 分钟

问题提出

#480 Sliding Window Median

如何在尽可能少的时间内找出一个数组的中位数？简单粗暴的做法是先排序，再按照次序选择相应的数据。这种算法的时间复杂度主要依赖于排序算法的复杂度，快排可以将其降到O(nlog(n))。

本文介绍一种时间复杂度为O(n)的算法。

主要思路

思路是寻找第n大的元素，在一个序列中确定第一个元素的位置，将其置于正确的位置（即它左边的元素都小于它，右边的元素都大于它）。假设这个位置是k，如果k=n，很幸运，已经找到了，算法结束；如果k<n，则递归的在左边寻找；如果k>n，则递归的在右边寻找。

代码（c++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
using std::cout;
using std::vector;
using std::swap;

int partition(vector<int> &list, int low, int high) {
    if (low == high) return low;
	int i = low, j = high + 1;
	int v = list[low];
	while (true) {
		while (list[++i] < v)
			if (i == high) break;
		while (list[--j] > v)
			if (j == low) break;
		if (i >= j) break;
		swap(list[i], list[j]);
	}
	swap(list[j], list[low]);
	return j;
}

int getMiddleNum(vector<int> &list, int k, int low, int high) {
	int j = partition(list, low, high);
	if (j == k) return list[k];
	if (j > k) return getMiddleNum(list, k, low, j - 1);
	return getMiddleNum(list, k, j + 1, high);
}

double getMiddleNum(vector<int> &list) {
	int size = list.size();
	if (size % 2 == 0)
		return getMiddleNum(list, size / 2 - 1, 0, size - 1) / 2.0 
             + getMiddleNum(list, size / 2, 0, size - 1) / 2.0;
	else
		return getMiddleNum(list, size / 2, 0, size - 1);
}

int main() {
	vector<int> list = {9, 2, 3, 6, 58};
	cout << getMiddleNum(list);
	return 0;
}

总结

这其实是利用了快排的思想，却做了一定的优化：毕竟不需要真正的排序，只需要找到特定位置的元素。

参考文章