网站 建设 汇报,基础网站怎么做,企业形象设计公司,在线浏览器入口临近期末#xff0c;鸭梨山大啊#xff0c;就不多说了。这道题的要求就是#xff0c;给定一串输入#xff0c;在中间任何一个时候#xff0c;都能够求出添加到一半的序列的中位数。 大概考虑一下#xff0c;如果用动态数组来进行元素插入的话#xff0c;尽管这样查询中位…临近期末鸭梨山大啊就不多说了。这道题的要求就是给定一串输入在中间任何一个时候都能够求出添加到一半的序列的中位数。 大概考虑一下如果用动态数组来进行元素插入的话尽管这样查询中位数的复杂度为O(1)由于每一次插入都是O(n)因而总复杂度为O(n^2)显然遭不住。如果用链表的话插入单次还是O(n)而且求中位数反而更不是O(1)了也不行。这时候注意到我们需要一个有序的序列来求中位数所以可以建两个set分别存放左半和右半序列由于set本身数据是有序的这样很容易就能查找到中位数了。 于是就可以写出如下代码 1 template typename T2 T last(setT _set)3 {4 return *(_set.rbegin());5 }6 7 template typename T8 T first(setT _set)9 {
10 return *(_set.begin());
11 }
12
13 class MedianFinder {
14 private:
15 setint left, right;
16 public:
17 //Adds a number into the data structure.
18 void addNum(int num) {
19 //Add new number first
20 if (left.empty()||(numlast(left)))
21 left.insert(num);
22 else
23 right.insert(num);
24
25 //Arrange left and right queue
26 if (left.size()right.size()2)
27 {
28 right.insert(last(left));
29 left.erase(last(left));
30 }
31 else if (left.size()right.size())
32 {
33 left.insert(first(right));
34 right.erase(first(right));
35 }
36 }
37
38 //Returns the median of current data stream
39 double findMedian() {
40 if (left.size()right.size())
41 return (last(left)first(right))/2;
42 else
43 return last(left);
44 }
45 }; 大家都知道C中set是用红黑树实现的于是每一次addNum都应该是O(log n)复杂度findMedian函数写的其实不够好因为每次添加过后其实都可以记录下当前的中位数避免到set中去查找最后一项现在复杂度是O(log n)如此重新设计之后能变成O(1) 不过悲催的是Leetcode还是Time Limit Exceeded了果然我是算法渣啊... 转载于:https://www.cnblogs.com/lqf-96/p/find-median-from-data-stream.html
