数组最中间值
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) { 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; } };
|