81. Data Stream Median

数组最中间值

LintCode链接

题目描述

输入的一组数字,返回每次输入新数字之后,该序列的最中间值

说明

最中间值的意思是指,一个有序数组的最中间的那个值。如果这个有序数组A的长度n为偶数,则中间值为A[n/2],如果为奇数,中间值为A[(n-1)/2]。例如:如果A=[1,2,3], 中间值为2. 如果A=[1,19], 中间值为1.

样例

给定输入数字为: [1, 2, 3, 4, 5], 返回 [1, 1, 2, 2, 3].
给定输入数字为: [4, 5, 1, 3, 2, 6, 0], 返回 [4, 4, 4, 3, 3, 3, 3].
给定输入数字为: [2, 20, 100], 返回 [2, 2, 20].

思路

将整个数组分为左边数组,中间值,右边数组
假设当前最中间值为mid,下个输入的值num
如果num <= mid,则num将插入在mid的左边数组,这时候需要判断:

  • 如果插入之前的长度为偶数,则插入之后,mid值不变,所以只需要简单的把num插入到左边数组即可
  • 如果插入之前的长度为奇数,则需要把mid插入到右边数组,然后把num插入到左边数组,再从左边数组找到一个最大值作为mid

同理,如果num > mid,则num将插入在mid的右边数组,这时候同样需要判断:

  • 如果插入之前的长度为偶数,则需要把mid插入到左边数组,然后把num插入到右边的数组,再从右边数组找到一个最小值作为mid
  • 如果插入之前的长度为奇数,则插入之后,mid值不变,所以只需要简单的把num插入到右边数组即可

至于如何维护左右两边的数组,从而可以快速的从其中获取到当前的最大最小值,可以使用最大最小堆来实现

代码

也可以使用优先队列来做,但是优先队列无法一开始就reserve,避免出现当nums比较大的时候重新开辟内存所带来的消耗

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public:
static bool less(int left, int right)
{
return left < right;
}

static bool greater(int left, int right)
{
return left > right;
}

vector<int> medianII(vector<int> &nums) {
// write your code here
vector<int> left, right, ret;
if (nums.empty())
{
return ret;
}

left.reserve(nums.size()), right.reserve(nums.size());

// 第一个;
int mid = nums[0];
ret.push_back(mid);

for (auto iter = nums.begin() + 1; iter != nums.end(); ++iter)
{
int num = *iter;
if (num <= mid)
{
if (ret.size() % 2 == 0)
{
// 当前处于偶数位;
left.push_back(num);
push_heap(left.begin(), left.end(), less);
}
else
{
// 当前处于奇数位;
right.push_back(mid);
push_heap(right.begin(), right.end(), greater);

left.push_back(num);
push_heap(left.begin(), left.end(), less);
pop_heap(left.begin(), left.end(), less);
mid = *left.rbegin();
left.pop_back();
}
}
else
{
if (ret.size() % 2 == 0)
{
// 当前处于偶数位;
left.push_back(mid);
push_heap(left.begin(), left.end(), less);

right.push_back(num);
push_heap(right.begin(), right.end(), greater);
pop_heap(right.begin(), right.end(), greater);
mid = *right.rbegin();
right.pop_back();
}
else
{
// 当前处于奇数位;
right.push_back(num);
push_heap(right.begin(), right.end(), greater);
}
}

ret.push_back(mid);
}

return ret;
}
};