给定一个int数组A，初始为空，现生成n个随机数依次传入数组中，将返回一个int数组，数组中的每个元素代表每次传入随机数到数组A后A中全部数的中位数。(若传入了偶数个数字则令中位数为第n/2小的数字，n为已传入数字个数)保证n小于等于1000。
测试样例：
[1,2,3,4,5,6],6
返回：[1,1,2,2,3,3]
[编程题]实时中位数
class Middle {
public:
vector<int> getMiddle(vector<int> A, int n) {
priority_queue<int, vector<int>, less<int>> small;
priority_queue<int, vector<int>, greater<int>> big;
vector<int> ans;
for(int i = 0; i < A.size(); ++i){
if(small.empty() || A[i] <= small.top())
small.push(A[i]);
else
big.push(A[i]);
if(small.size() == big.size()+2){
big.push(small.top());
small.pop();
}
else if(small.size() == big.size()-1){
small.push(big.top());
big.pop();
}
ans.push_back(small.top());
}
return ans;
}
};
发表于 2015-10-12 15:38:25
回复(2)
class Middle {
public:
vector<int> getMiddle(vector<int> A, int n) {
//第奇数个数插入最小堆minheap,第偶数个数插入最大堆maxheap,
//奇数个时中位数为minheap的堆顶元素，偶数个时中位数为maxheap的堆顶元素
//push_heap,pop_heap是STL提供的函数，最大/最小堆都存在vector中
//先处理前两个元素以及特殊情况
vector<int> res(n);
if (n<1)
return res;
res[0] = A[0];
if (n == 1)
return res;
if (A[1] > A[0])
{
maxheap.push_back(A[0]);
minheap.push_back(A[1]);
}
else
{
maxheap.push_back(A[1]);
minheap.push_back(A[0]);
}
res[1] = maxheap[0];
//依次插入到最大堆和最小堆
for (int i = 2; i<n; ++i)
{
int num = A[i];
if (i % 2)//第偶数个，插入最大堆maxheap
{
if (num >minheap[0])
{
minheap.push_back(num);
push_heap(minheap.begin(), minheap.end(), greater<int>());
num = minheap[0];
pop_heap(minheap.begin(), minheap.end(), greater<int>());
minheap.pop_back();
}
maxheap.push_back(num);
push_heap(maxheap.begin(), maxheap.end(), less<int>());
res[i] = maxheap[0];
}
else//第奇数个，插入最小堆minheap
{
if (num <maxheap[0])
{
maxheap.push_back(num);
push_heap(maxheap.begin(), maxheap.end(), less<int>());
num = maxheap[0];
pop_heap(maxheap.begin(), maxheap.end(), less<int>());
maxheap.pop_back();
}
minheap.push_back(num);
push_heap(minheap.begin(), minheap.end(), greater<int>());
res[i] = minheap[0];
}
}
return res;
}
private:
vector<int> minheap;
vector<int> maxheap;
};
发表于 2017-07-11 16:52:58
回复(0)
//插入排序 维护前面部分有序
vector<int> getMiddle(vector<int> A, int n) {
vector<int>ans;
ans.push_back(A[0]);
for(int i=1;i<n;++i){
int j;
for(j=i-1;j>=0;--j){
if(A[i]>=A[j])break;
}
A.insert(A.begin()+j+1,A[i]);
A.erase(A.begin()+i+1);
ans.push_back(A[i/2]);
}
return ans;
}
发表于 2019-09-08 00:12:13
回复(0)
multiset自动排序，advance前进指针，vans
class Middle {
public:
vector<int> getMiddle(vector<int> A, int n) {
// write code here
vector<int> res;
if(n<=0)return res;
multiset<int> ms;//自动排序
for(int i=0;i<n;i++){
ms.insert(A[i]);
auto it=ms.begin();
advance(it,i>>1);//前进合适距离
res.push_back(*it);//放入中位数
}
return res;
}
};
发表于 2019-02-28 20:21:09
回复(2)
import java.util.*;
public class Middle {
public int[] getMiddle(int[] A, int n) {
// write code here
int res[]=new int[n];
res[0]=A[0];
for(int i=1;i<n;i++){
List<Integer> list=new ArrayList<>();
for(int j=0;j<=i;j++){
list.add(A[j]);
}
Collections.sort(list);
res[i]=list.get(i/2);
}
return res;
}
}
public class Middle {
public int[] getMiddle(int[] A, int n) {
// write code here
int res[]=new int[n];
res[0]=A[0];
for(int i=1;i<n;i++){
List<Integer> list=new ArrayList<>();
for(int j=0;j<=i;j++){
list.add(A[j]);
}
Collections.sort(list);
res[i]=list.get(i/2);
}
return res;
}
}
发表于 2018-03-18 19:43:03
回复(0)
class Middle {
public:
vector<int> getMiddle(vector<int> A, int n) {
vector<int> res;
priority_queue<int> mins;
priority_queue<int,vector<int>,greater<int> > maxs;
for(int i=0;i<n;i++){
if(mins.empty()||A[i]<=mins.top()) mins.push(A[i]);
else maxs.push(A[i]);
if(mins.size()-maxs.size()==2)
maxs.push(mins.top()),mins.pop();
if(maxs.si***s.size()==1)
mins.push(maxs.top()),maxs.pop();
res.push_back(mins.top());
}
return res;
}
};
发表于 2017-11-15 12:24:18
回复(0)
用最大最小堆维护
class Middle {
public:
vector<int> getMiddle(vector<int> A, int n)
{
if (n == 1) return vector<int>{A[0]};
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
vector<int> res(n);
res[0] = A[0];
res[1] = min(A[0], A[1]);
maxHeap.emplace(min(A[0], A[1]));
minHeap.emplace(max(A[0], A[1]));
for (int i = 2; i < n; ++i)
{
if (A[i] >= minHeap.top()) minHeap.emplace(A[i]);
else maxHeap.emplace(A[i]);
if ((i & 1) == 1)
{
if (maxHeap.size() > minHeap.si敏感词Heap.emplace(maxHeap.top());
maxHeap.pop();
}
else if (maxHeap.size() < minHeap.size())
{
maxHeap.emplace(minHeap.top());
minHeap.pop();
}
res[i] = maxHeap.top();
}
else
{
if (maxHeap.size() + 1 > minHeap.si敏感词Heap.emplace(maxHeap.top());
maxHeap.pop();
}
else if (maxHeap.size() + 1 < minHeap.size())
{
maxHeap.emplace(minHeap.top());
minHeap.pop();
}
res[i] = minHeap.top();
}
}
return res;
}
};
发表于 2017-07-02 17:37:39
回复(0)
/*
建立最大最小堆，具体步骤如下：
1、最大堆中存放比最小堆中小的元素
2、如果最大堆中队头的元素大于最小堆的元素，则交换
3、i为奇数时存入最小堆，否则在最大堆中
*/
import java.util.*;
public class Middle {
public int[] getMiddle(int[] A, int n) {
// write code here
if(A==null || n<1)
return null;
int[] res = new int[n];
Comparator<Integer> cmp = new Comparator<Integer>() {
@Override
public int compare(Integer i1,Integer i2) {
return i2.compareTo(i1);
}
};
PriorityQueue<Integer> maxHeap = new PriorityQueue(n,cmp);
PriorityQueue<Integer> minHeap = new PriorityQueue(n);
for(int i=0;i<n;i++) {
maxHeap.offer(A[i]);
if(i%2==1) {
minHeap.offer(maxHeap.poll());
//res[i] =(maxHeap.peek()+minHeap.peek())/2;
} else{
if(!minHeap.isEmpty()){
if(maxHeap.peek()>minHeap.peek()) {
Integer ma = maxHeap.poll();
Integer mi = minHeap.poll();
maxHeap.offer(mi);
minHeap.offer(ma);
}
}
}
res[i] = maxHeap.peek();
}
return res;
}
}
发表于 2016-07-21 10:15:22
回复(0)
class Middle {
public:
vector<int> getMiddle(vector<int> A, int n) {
// write code here
if(A.size()<=1)
return A;
if(A.size()!=n)
return A;
set<int,greater<int>> mleft;
set<int> mright;
int temp;
vector<int> mid;
mleft.insert(A[0]);
auto begleft = mleft.begin();
auto begright = mright.begin();
int leftsize = mleft.size();
int rightsize = mright.size();
mid.push_back(*begleft);
for(int i=1;i<n;++i)
{
if(leftsize-rightsize==1)//将节点插入右子树
{
if(A[i]>=*begleft)//保证左子树的最大值小于右子树的最小值
mright.insert(A[i]);
else
{
temp = *begleft;
mright.insert(temp);
mleft.erase(begleft);
mleft.insert(A[i]);
}
}
else
if(leftsize==rightsize)//两个树的节点数目相同，那么插入左子树
{
if(A[i]>=*begright)
{
temp = *begright;
mleft.insert(temp);
mright.erase(begright);
mright.insert(A[i]);
}
else
mleft.insert(A[i]);
}
//每次使用完后必须要更新迭代器和节点数目
begleft= mleft.begin();//左子树的最大值
begright = mright.begin();//右子树的最小值
leftsize = mleft.size();
rightsize = mright.size();
mid.push_back(*begleft);
}
return mid;
}
};
发表于 2015-09-09 15:10:27
回复(0)
class Middle {
public:
vector<int> getMiddle(vector<int> A, int n) {
// write code here
vector<int> B = {A[0]};
vector<int> C = {A[0]};
int num = 1;
for(int i=1;i<n;i++){
for(int j = num;j>=0;j--){
if(0==j||A[i]>B[j-1]){
B.insert(B.begin()+j,A[i]);
break;
}
}
C.push_back(B[i/2]);
num++;
}
return C;
}
};
题目要求《对于每次传入一个数字后，算出当前所有传入数字的中位数
》即动态生成，B用于排序，这里使用二分查找然后调用B.insert()比较好，本人又一次手懒了用插入排序的；每次排序后
C.push_back(B[i/2])将结果装入C中；最后的C便是返回的结果
发表于 2015-08-07 12:54:15
回复(0)
python solution
使用bisect模块，时间复杂度为nlogn
# -*- coding:utf-8 -*-
import bisect
class Middle:
def getMiddle(self, A, n):
mid,res,count=[],[],0
for i in A:
bisect.insort(mid,i)
count+=1
if count%2==0:
res.append((mid[count//2-1]))
else:
res.append(mid[count//2])
return res
编辑于 2017-10-31 16:41:28
回复(0)
//插入排序
import java.util.*;
public class Middle {
public int[] getMiddle(int[] A, int n) {
// write code here
int[]res=new int[A.length];
res[0]=A[0];
for (int i = 1; i < A.length; i++) {
int k=i-1;
int tem=A[i];
while(k>=0&&A[k]>tem){
A[k+1]=A[k];
k--;
}
A[++k]=tem;
res[i]=A[i/2];
}
return res;
}
}
发表于 2016-08-13 15:52:24
回复(0)
//和剑指offer 63题类似，借助了以前做的，用的最大堆最小堆。
class Middle {
private:
vector<int> min;
vector<int> max;
public:
void Insert(int num)
{
//如果数据是偶数个
int min_si敏感词.size();
int max_size=max.size();
int total=min_size+max_size;
if(total%2==0){ //如果数据是偶数个,最终要插入到最小堆
if(max_size>0&&num<max[0]){
//必须要数据元素大于0
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());
num=max[0];
pop_heap(max.begin(),max.end(),less<int>());
max.pop_back();
}
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
}
else{
if(min_size>0&&num>min[0]){
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
num=min[0];
pop_heap(min.begin(),min.end(),greater<int>());
min.pop_back();
}
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());
}
}
int GetMedian()
{
int si敏感词.size()+max.size();
if(size==0) return -1;
int median;
if(size%2)
median=min[0];
else
median=max[0];
return median;
}
vector<int> getMiddle(vector<int> A, int n) {
// write code here
vector<int> result;
if(n<=0) return result;
for(int i=0;i<n;++i){
Insert(A[i]);
result.push_back(GetMedian());
}
return result;
}
};
发表于 2015-10-05 21:08:14
回复(2)
import java.util.*;
public class Middle {
public int[] getMiddle(int[] A, int n) {
// write code here
int[] result = new int[A.length];
int count = 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((x, y) -> y - x);
for (int i = 0; i < A.length; ++i) {
if ((count & 1) == 0) {
maxHeap.offer(A[i]);
Integer filteredMaxNum = maxHeap.poll();
minHeap.offer(filteredMaxNum);
} else {
minHeap.offer(A[i]);
Integer filteredMinNum = minHeap.poll();
maxHeap.offer(filteredMinNum);
}
result[i] = (count & 1) == 0 ? minHeap.peek() : maxHeap.peek();
count += 1;
}
return result;
}
}
发表于 2018-08-02 20:11:46
回复(0)
import java.util.*;
public class Middle {
public int[] getMiddle(int[] A, int n) {
// write code here
int res[] = new int[n];
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((u, v) -> v.compareTo(u));
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
maxHeap.offer(A[i]);
minHeap.offer(maxHeap.poll());
if (maxHeap.size() < minHeap.size()) {
maxHeap.offer(minHeap.poll());
}
res[i] = maxHeap.peek();
}
return res;
}
}
编辑于 2024-03-01 15:33:35
回复(0)
class Middle {
public:
vector<int> getMiddle(vector<int> A, int n) {
// write code here
vector<int> ret;
multiset<int> nums;
multiset<int>::iterator itr;
for (int i = 0; i < n; ++i) {
if (nums.empty() ) {
ret.push_back(A[i]);
nums.insert(A[i]);
} else {
nums.insert(A[i]);
int k = i / 2;
itr = nums.begin();
while (k > 0) {
--k;
++itr;
}
ret.push_back(*itr);
}
}
return ret;
}
};
发表于 2020-08-02 16:00:32
回复(0)
import java.util.*;
public class Middle {
public int[] getMiddle(int[] A, int n) {
int[] res = new int[n];
PriorityQueue<Integer> max = new PriorityQueue<>((o1, o2) -> o2 - o1);
PriorityQueue<Integer> min = new PriorityQueue<>();
max.add(A[0]);
res[0] = A[0];
for (int i = 1; i < n; i++) {
if (A[i] <= res[i - 1]) {
max.add(A[i]);
} else
min.add(A[i]);
if (min.size() > max.size()) {
max.add(min.poll());
}
if (max.size() - 1 > min.size()) {
min.add(max.poll());
}
res[i] = max.peek();
}
return res;
}
}
发表于 2020-04-24 20:53:13
回复(0)
Python Solution
有点无耻的解法，完全模拟挨个输入：
class Middle:
def getMiddle(self, A, n):
# write code here
result = []
tmp = []
for i in range(0,n):
tmp.append(A[i])
tmp.sort()
result.append(tmp[i//2])
return result
def getMiddle(self, A, n):
# write code here
result = []
tmp = []
for i in range(0,n):
tmp.append(A[i])
tmp.sort()
result.append(tmp[i//2])
return result
发表于 2019-11-19 20:50:19
回复(0)
问题信息
难度：
47条回答
53收藏
14094浏览
通过挑战的用户
查看代码-
2022-08-24 09:02:40 -
2022-08-21 12:30:58
-
2022-07-25 11:55:58
-
2022-06-28 13:42:34 -
2022-06-07 12:28:30
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
