- 问题来源
- 问题简介
从一个无序数组中寻找中位数。
解题思路
当我们从无序数组中寻找第k个数时（k = {1, 2, …}），我们可以先将数组排成有序的，再直接下标索取就可以了。
这样子虽然可行，却是做了很多多余的事，我们并不关心数组是否有序，只是想知道第k个数是什么而已。我们可以这样：
从数组 arr 中随机选一个数 num，则可以将该无序数组分为3类：
- a[l]: 小于num的数
- a[v]: 等于num的数
- a[l]: 大于num的数
若：
- k在a[l]中
- 则问题转化为在a[l]中寻找第
k个数 - k在a[v]中
- 则返回 num
- k在a[r]中
- 则问题转化为在a[l]中寻找第
k-a[l].length-a[v].length个数
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(未知) | O(未知) |
Code
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
arr.push_back(num);
}
double findMedian() {
int s = size();
if ((s & 1)) {
return findKthNum(s / 2 + 1);
}
else {
return (findKthNum(s / 2) + findKthNum(s / 2 + 1)) / 2;
}
}
int size() {
return arr.size();
}
private:
vector<int> arr;
double findKthNum(int k) {
int s = size();
if (s == 0 || k > s) {
throw "invalid length";
}
if (s == 1) {
return arr[0];
}
MedianFinder l, v, r;
int key = arr[k-1];
for_each(arr.begin(), arr.end(), [&](int num) {
if (num < key) {
l.addNum(num);
}
else if (num == key) {
v.addNum(num);
}
else {
r.addNum(num);
}
});
if (l.size() >= k) {
return l.findKthNum(k);
}
else if (v.size() >= k - l.size()) {
return key;
}
else {
return r.findKthNum(k - l.size() - v.size());
}
}
};
int main() {
MedianFinder obj;
obj.addNum(1);
obj.addNum(3);
obj.addNum(7);
obj.addNum(5);
cout << obj.findMedian() << endl;
obj.addNum(2);
cout << obj.findMedian() << endl;
return 0;
}
