描述
本题将给出一个整数数据流,你将实现如下两个函数:
add(val)
:从数据流中获得一个数字。getMedian()
:返回你从数据流获得的所有数字的 中位数
。本题的 中位数
不等同于数学定义里的 中位数
。
本题的中位数是指将所有数字排序后得到数组的中间值,如果有数组 A
中有 n
个数,则中位数为 A[(n - 1) / 2]
。
比如:数组 A=[1,2,3]
的中位数是 A[(3-1)/2] = A[1] = 2
,数组 A=[1,19]
的中位数是 A[(2-1)/2] = A[0] = 1
。
4轮面试3轮遇原题!
《Amazon高频题礼包》刷完上岸率翻倍!
微信添加【jiuzhang0607】备注【Amazon】领取
数据流中的数字数量不会超过 10^4104 个。
样例
样例 1:
输入:
- add(1)
- getMedian()
- add(2)
- getMedian()
- add(3)
- getMedian()
- add(4)
- getMedian()
- add(5)
- getMedian()
输出:
- 1
- 1
- 2
- 2
- 3
解释:
[1] 和 [1,2] 的中位数是 1,
[1,2,3] 和 [1,2,3,4] 的中位数是 2,
[1,2,3,4,5] 的中位数是 3。
样例 2:
输入:
- add(4)
- getMedian()
- add(5)
- getMedian()
- add(1)
- getMedian()
- add(3)
- getMedian()
- add(2)
- getMedian()
- add(6)
- getMedian()
- add(0)
- getMedian()
输出:
- 4
- 4
- 4
- 3
- 3
- 3
- 3
解释:
[4], [4,5] 和 [4,5,1] 的中位数是 4,
[4,5,1,3], [4,5,1,3,2], [4,5,1,3,2,6] 和 [4,5,1,3,2,6,0] 的中位数是 3。
挑战
实现一个时间复杂度为 O(n*logn)O(n∗logn) 的算法
vector
int findLeftMax(vector
{
//二分查找
int left = 0;
int right = ret.size() - 1;
int mid = (left + right) / 2;
while (left
if (val > ret[left])
{
if (left + 1 <= right )
{
if (ret[left + 1] < val && val > ret[mid])
{
left = mid + 1;
}
else
{
left = left + 1;
}
}
}
else if (val < ret[left])
{
right = mid;
}
else if (val == ret[left])
{
return left;
}
if (left >= right)
{
if (val > ret[right])
{
return left + 1;
}
return left;
}
mid = (left + right) / 2;
}
return left;
}
void add(int val) {
// write your code here
if (ret.size() == 0)
{
ret.push_back(val);
return;
}
if (ret.size() == 1)
{
if (ret[0] > val)
{
int tmp = ret[0];
ret.pop_back();
ret.push_back(val);
ret.push_back(tmp);
return;
}
else
{
ret.push_back(val);
return;
}
}
//开头
if (val < ret[0])
{
ret.insert(ret.begin(), val);
return;
}
//结尾
if (val > ret[ret.size()-1])
{
ret.push_back(val);
return;
}
int index = findLeftMax(ret, val);
ret.insert(ret.begin() + index, val);
}
int getMedian() {
// write your code here
return ret[(ret.size() - 1) / 2];
return 0;
}