小编sac*_*hin的帖子

问题 M号的中位数被定义为1)如果M是按顺序排序后的奇数中间数2)如果M是中间2个数的平均数(排序后再次)你首先有一个空数字列表.然后,您可以在列表中添加或删除一些数字.对于每个添加或删除操作,输出列表中的数字中位数.

示例:对于一组m = 5的数字,{9,2,8,4,1},中位数是排序集{1,2,4,8,9}中的第三个数字,即4. m = 4,{5,2,10,4},中位数是排序集{2,4,5,10}中第二和第三个元素的平均值,即(4 + 5)/ 2 = 4.5

我的方法 我认为问题可以用这种方式解决.想法是使用先前的中值和指针来找到新的中值而不是在每次添加或删除操作时重新计算.

1)使用多重集合,它始终按顺序保留元素并允许重复.换句话说,以某种方式维护排序列表.

2)如果添加操作

2.1) Insert this element into set and then calculate the median

2.2) if the size of set is 1 then first element will be the median

2.3) if the size of set is even, then

           if new element is larger then prev median, new median will be avg of prev median

               and the next element in set.

           else new median will be avg …

如何打印二叉树的外框.

1. 订单从上到下,从左到右,然后从下到上
2. 打印所有leftest节点和最正常的节点
3. 打印所有叶节点

4. 打印只有1个叶子的所有节点

            100
           /   \ 
         50     150
        / \      /
      24   57   130
     /  \    \    \
   12   30    60   132
   

   Run Code Online (Sandbox Code Playgroud)

例如:输出应为100,50,24,12,30,57,60,130,132,150

如果我们编写三个不同的函数来打印左节点,叶节点和右节点,它可以很容易地解决,但需要O(n + 2logn)时间.

我也在寻找O(n)方法,但条件是每个节点只应访问一次,不需要额外的O(2logn)部分.