金山云笔试，结构体函数
今天做了金山云的笔试，最后一道题结构体函数写了个链表很low，所以在这里写个较完善的。
1、设计一个结构体Data，要求AddData(int x)可以实现插入一个正整数
2、设计函数Double midData()返回数据结构中的中位数，如果元素个数为基数返回中间值，如果为偶数返回中间两个数的平均值。
（好似有三问，其中一问是设计数据结构。。。）
struct DATA{//数据结构中添加一个结构体函数vector<int> num;void AddData(int x);
};void DATA::AddData(int x){//结构体函数num.push_back(x);
}
void quicksort(vector<int> &ss,int tail,int head){//使用快排将数组中的数排序int i,j;i=tail;j=head;if(i>=j) return;int tmp=ss[i];while(iwhile(itmp) j--;if(iwhile(iif(i1,head);
}
double midData(vector<int > ss){//找中位数int n=ss.size();if(n%2==0) return (ss[n/2-1]+ss[n/2])/2.0;if(n%2==1) return ss[n/2-1];
}
int _tmain(int argc, _TCHAR* argv[])
{DATA first;for(int i=10;i>0;i--)first.AddData(i);vector<int> tmpnum=first.num;quicksort(tmpnum,0,tmpnum.size()-1);cout< 返回值5.5
经过小伙伴点拨，发现这种方法更好故贴出来
使用堆来实现数据的存储，一个大顶堆，一个小顶堆
class Solution {
public:struct Data{priority_queue<int> less;//小顶堆priority_queue<int,vector<int>, greater<int> > max;//大顶堆}s;void Insert(int num){int tmp;if(count%2==0){//为偶数时先存入小顶堆，在把小顶堆的top push 大顶堆s.less.push(num);tmp=s.less.top();s.less.pop();s.max.push(tmp);}else if(count%2==1){//为偶数时先存入大顶堆，在把大顶堆的top push 小顶堆s.max.push(num);tmp=s.max.top();s.max.pop();s.less.push(tmp);}count++;}
//为什么要这么分呢，这样保证了小顶堆中都是大于等于中位数值，且top为所有值中最小的
//同时保证了大顶堆都是小于中位数的值，且top为所有值中最大的
//如此就很容易的取出中间值了double GetMedian(){ if(count%2==1) return s.max.top();else return (s.less.top()+s.max.top())/2.0;}
private:int count=0;
};这么简单的题没做出来，对于结构体的认识还是不够完善。
继续努力
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！