精华内容
下载资源
问答
  • 数据流中获取中位数

    万次阅读 2020-02-29 11:55:55
    数据流中获取中位数需求描述需求分析C++代码如下python代码 需求描述   有一个动态的数据流,如何比较快的获得数据流的中位数。这个过程中,数据流可能会有新的数据加入。中位数定义为元素个数为奇数的序列的...

    需求描述

      有一个动态的数据流,如何比较快的获得数据流的中位数。这个过程中,数据流可能会有新的数据加入。中位数定义为元素个数为奇数的序列的排序结果中间位置元素值,偶数数列的排序结果中间位置的两个元素的元素值的平均。

    需求分析

      首先要获得数据流的中位数,这个问题可以轻易转换成查找序列中的第k大的数,如果序列长度为偶数,则要查找两次,但是不会影响复杂度。但是现在还要处理的一个问题是,这个数据流的元素个数会增加的,元素一旦增加,很可能中位数就变了,如果再要获得就不会很方便。我们采用这个办法的话,就得重新查找中位数。
      总结来看,我们查找一次中位数的时间复杂度是O(n)O(n),分析在链接中的文章写得很清楚了。维护这样的数据流,每新来一个数据插入数据的时间复杂度就是O(1)O(1)了。因为要使用partition函数,所以这个数据流需要是顺序表的结构。
      可能要多次查找中位数,我们维持一个排序的序列,要查找中位数只需要O(1)O(1)的时间复杂度。因为如果是顺序表的话,直接随机存储访问中间元素即可,如果是链表,我们需要设置两个指针,来指向中间元素,插入元素后这两个指针最多向后移动一个元素,不带来额外的复杂度。但是使用排序的线性结构,新插入的元素直接插入会破坏排序结构,所以只能找好位置再插入,在排序的线性结构中插入一个元素,并继续维持有序,插入的时间复杂度就是O(n)O(n),分析可以参考插入排序(可见排序算法的重要性了)。这种方式可以通过顺序表或者链表实现。
      完成这个问题,可以把问题分成两部分,那就是查找中位数,和插入数据。继续检索其他数据结构来完成这两个任务,平衡二叉树(平衡二叉树一定是二叉搜索树)可以在O(1)O(1)的时间插入元素,在O(lgn)O(lgn)的时间内查找指定元素。但是这里显然,我们不确定中位数,没法直接查找,我们可以思考如何对数据结构进行扩充来实现这种操作。
      平衡二叉树的定义是自己以及所有子树的 左右子树的高度差是{-1,0,1}的二叉搜索树《剑指offer》 中提到了通过扩充平衡二叉树,将定义改为任意子树的左右子树节点数差是{-1,0,1}的二叉搜索树。经过我的仔细分析,这个是无法实现的。因为我们所知的平衡二叉树,因为插入节导致的不平衡状态总结起来有四种,分别是我们所知道的LL, LR, RR, RL型不平衡。但是修改定义之后的平衡二叉树因为插入节点而导致的不平衡状态有无数种。平衡二叉树满足很好的递归性质,调整不平衡的时候是不需要上溯的,按照对应情况进行旋转即可。但是修改定义之后的二叉树不平衡调整是需要上溯的。以上两点理由决定了这种扩充无法实现(这是我个人的分析,欢迎讨论)。
      树虽然性质很优,但是很难用来查找中位数。
      我个人的思考就是继续使用平衡二叉树,但是给数的节点保存一个额外的字段,就是孩子节点的总数。插入节点的时候在哪个子树插入,就把插入位置的查找路径上每个节点的孩子节点数+1。如果遇到因为插入导致的不平衡状态,在平衡旋转的时候也要做特殊处理,这个子节点数目调整很容易实现。以LL型平衡旋转为例,左子节点顶替了父亲的位置,节点数变为父节点的数目。父节点变为左子节点的右孩子,子点数目为自己当前两个孩子之和+1。其余节点的子节点数目不变。可见这个过程不会增加复杂度的量级。
      通过这种方式的实现,可以知道插入一个节点的复杂度是O(lgn)O(lgn),找中位数的复杂度是O(lgn)。这个过程略微复杂,我就不贴代码,欢迎讨论。
      再继续分析,我们要求中位数,无非最多就是找两个数,如果我们把整个序列想象成排好序的序列,用这两个数把整个数据分段的话,这两个数分分别是前半段序列中最大的元素,后半段序列中的最小元素。也就是说,我们本可以不用去对序列排序,只需要方便找出最大和最小元素即可。
    中位数分析图
      树中还有一种特殊的结构叫堆,可以很快的查找出树中的最大/最小元素。但是一个堆找最大,一个堆找最小,我们就需要两个堆了,而且大顶堆的所有元素都小于小顶堆的所有元素。我们进一步分析发现,把中间部分较小的数放在第一个堆里,是第一个堆中最大的,我们使用大顶堆。中间部分较大的数放在第二个堆里,是第二个堆中最小的,我们使用小顶堆。这样就可以在O(1)O(1)的时间内求出中位数。
      这是序列长度为偶数的情况,如果长度为奇数,则只需要查找一个元素,我们可以让中间元素就是大顶堆的堆顶,这个时候,大顶堆包括了中间元素以及前半段,小顶堆只包含了后半段。大顶堆大序列数目比小顶堆多1。我们在插入的时候保证,总元素个数为奇数,则大顶堆比小顶堆元素多一个。
      我们进一步看看如何维护这两个堆,也就是插入的过程。总结来说,如果元素总个数为奇数,我们应该是大顶堆多一个元素。如果小顶堆的堆顶大于要插入的数,显然这个数出现在排序序列的前半段,可以直接将其插入大顶堆,然后调整堆即可。如果插入的数大于小顶堆堆顶,这个数据应该出现在序列的后半段,但是如果我们将其插入小顶堆,显然不符合我们的大顶堆的元素个数比小顶堆多的预设。我们这个时候,就得减少小顶堆的长度了。显然是小顶堆弹出堆顶,然后调整堆。这个堆顶的数现在应该去大顶堆了,然后插入大顶堆,调整堆。
      如果两个堆的总数目为奇数,根据我们的预设,大顶堆比小顶堆元素多1,现在要往小顶堆插入,分析就与上面的分析类似了。仍然是先判断插入元素是否小于大顶堆,判断插入的数应该出现在什么位置。如果这个数插入到大顶堆,大顶堆就得弹出堆顶,堆顶元素进入小顶堆。

    C++代码如下

    #include<vector>
    #include<algorithm>
    using namespace std;
    
    template<typename T>class DynamicArray
    {
    public:
    	void Insert(T num)
    	{
    		if (min.size() ^ max.size())
    		{
    			if (num < max[0])
    			{
    				max.push_back(num);
    				push_heap(max.begin(), max.end(), less<T>());
    				num = max[0];
    				pop_heap(max.begin(), max.end(), less<T>());
    				max.pop_back();
    			}
    			min.push_back(num);
    			push_heap(min.begin(), min.end(), greater<T>());
    		}
    		else
    		{
    			if (min.size() && num > min[0])
    			{
    				min.push_back(num);
    				push_heap(min.begin(), min.end(), greater<T>());
    				num = min[0];
    				pop_heap(min.begin(), min.end(), greater<T>());
    				min.pop_back();
    			}
    			max.push_back(num);
    			push_heap(max.begin(), max.end(), less<T>());
    			is_heap()
    		}
    	}
    	T getMedian()
    	{
    		if (!max.size())
    			throw exception("No elements are available");
    
    		if (min.size() ^ max.size())
    		{
    			return max[0];
    		}
    		else
    		{
    			return (max[0] + min[0]) / 2;
    		}
    	}
    private:
    	vector<T>min;
    	vector<T>max;
    };
    

    python代码

    def less(left, right):
        return left<right
    
    def greater(left,right):
        return left>right
    
    def siftup(heap, startpos, pos,func=less):
        newitem = heap[pos]
        while pos>startpos:
            parentpos = (pos - 1) >> 1
            parent = heap[parentpos]
            if func(parent,newitem):
                heap[pos] = parent
                pos = parentpos
                continue
            break
        heap[pos] = newitem
    
    def siftdown(heap, pos,func=less,endpos=None):
        if endpos is None:
            endpos=len(heap)
        newitem = heap[pos]
        childpos = 2*pos + 1    # leftmost child position
        while childpos<endpos:
            rightpos = childpos + 1
            if rightpos<endpos and func(heap[childpos],heap[rightpos]):
                childpos = rightpos
            if func(newitem,heap[childpos]):
                heap[pos] = heap[childpos]
                pos = childpos
                childpos = 2*pos + 1
            else:
                break
    
        heap[pos] = newitem
    
    def heappush(heap, item,func=less):
        heap.append(item)
        siftup(heap, 0, len(heap) - 1,func)
    
    def heappop(heap,func=less):
        lastelt = heap.pop()
        if heap:
            returnitem = heap[0]
            heap[0] = lastelt
            siftdown(heap, 0,func)
            return returnitem
        return lastelt
    
    
    class DymaicArray():
        _min=[]
        _max=[]
        def getMedian(self):
            if not self._max:
                raise Exception('No elements are available')
            if len(self._max) ^ len(self._min):
                return self._max[0]
            else:
                return (self._max[0]+self._min[0])/2
    
        def insert(self,num):
            if len(self._max) ^ len(self._min):
                if num<self._max[0]:
                   heappush(self._max,num,less)
                   num=heappop(self._max,less)
                heappush(self._min,num,greater)
            else:
                if self._min and num>self._min[0]:
                    heappush(self._min,num,greater)
                    num=heappop(self._min,greater)
                heappush(self._max,num,less)
    

      python采用了自己实现大顶堆,小顶堆,所以代码就更加长一些。
      最后总述一下使用两个堆来操作的复杂度,求中位数就是取两个堆顶,时间复杂度是O(1)O(1),然后维护这样的堆,当有数据插入的时候时间复杂度是O(lgn)O(lgn),可见这种做法还是相当优秀的。下面表格将这几种算法的特性详细列出来。

    基础数据结构 元素插入时间复杂度 取中位数的时间复杂度 特点描述
    无序数组 O(1)O(1) O(n)O(n) 插入时间复杂度最小,适合频繁插入
    有序线性表(数组,链表) O(n)O(n) O(1)O(1) 查找快,但是数据结构的维护困难
    平衡二叉树 O(lgn)O(lgn) O(lgn)O(lgn) 查找和维护相对均衡,但是存储的额外信息多(指针,子节点数),查找其他元素也很快
    最大堆和最小堆 O(lgn)O(lgn) O(1)O(1) 非常好的一种实现,但是查找其他元素效率低
    展开全文
  • 数据流中的中位数

    千次阅读 2018-07-02 11:28:58
    题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。由于...

    题目描述

            如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

    由于数据是从一个数据流中读出来,因而数据的数目随着时间的增加而增加,如果用一个数据容器来保存从流中读出来的数据,则当新的数据从流中读出来的时候,这些数据就插入数据容器。这个数据用什么数据结构定义合适呢?接下来讨论一下最合适的数据结构:

    首先,先用一个表格列出可用数据结构的各复杂度

     

    不同数据结构的时间复杂度
    数据结构 插入的时间复杂度 得到中位数的时间复杂度
    没有排序的数组 O(1) O(n)
    排序的数组 O(n) O(1)
    排序的链表 O(n) O(1)
    二叉搜索树 平均O(logN),最差O(n) 平均O(logN),最差O(n)
    VAL树 O(logN) O(1)
    最大堆和最小堆 O(logN) O(1)

    接下来,细细分析一下:

     

    1. 数组是最简单的数据容器。如果数组没有排序,那么可以用前面提到的Partition函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度分别是O(1)和O(n)。
    2. 在往数组里插入数字的时候我们可以让数组保持排序。这时由于可能需要移动O(n)个数字,因此需要O(n)的时间复杂度。在已排好的数组中取中位数,我们只需要O(1)的时间复杂度即可。
    3. 排序的链表是另外一种选择,我们需要O(n)的时间复杂度才能在链表中找到其合适的位置插入新的数据。如果定义两个指针指向链表中间的节点,那么可以在O(1)的时间内得出中位数。
    4. 二叉搜索树可以把插入新数据的平均时间复杂度降低到最低,但是由于二叉搜索树极度不平衡,从而看起来像一个排序的链表的时候,插入新数据的时间仍然是O(n),为了得到中位数,可以在二叉树节点中添加一个表示子树节点数目的字段。有了这个字段,可以在平均O(logN)时间内得到中位数,但最差情况仍然是O(logN)。
    5. 为了避免二叉搜索树的最差情况,可以利用平衡的二叉搜索树,即VAL树。通常VAL树的平衡因子是左右子树的高度差。可以稍作修改,把VAL树的平衡因子改为左右子树节点数目之差。有了这个改动,可以用O(logN)时间往VAL树中添加一个新节点,同时用O(1)时间得到所有节点的中位数。
    6. 虽然VAL树的效率很高,但是大部分编程语言的函数库是没有实现这个数据结构的,在面试期间短短几十分钟也是不可能实现这个功能的,所以只能考虑其他办法。

     

    从上图可以看到,如果容器中数据的数目是奇数,那么两个指针指向同一个数据。

    我们可以发现,整个数据容器被分成两个部分。位于容器左边部分的数据结构比右边的数据结构小。另外,p1指针指向的数据是左边部分最大的数,p2指向的是右边部分最小的数。

     

            OK,找出最优的数据结构后,我们再考虑一点细节。首先要保证数据平均分配到两个堆中,因此两个堆中的数据的数目之差不能为1。为了实现平均分配,可以在数据的总数目是偶数的情况下把新数据插入最小堆,否则插入最大堆。

            还要保证最大堆的所有数都大于最小堆,因此按照前面的分配规则,会把新的数据插入最小堆。如果此时插入最小堆的数据大于最大堆的最小值,那么它就不能成为最小堆的数据,因此我们需要把这个新数据先插入最大堆,然后取出最大堆里最小值min,再把找到min插入最小堆中,以此来满足我们的规则——最小堆中所有数字都小于最大堆的数字。同理可插入新数据进入最大堆。

    以下为C#实现的代码,用两个list作为堆容器来实现的:

    
    using System;
    using System.Collections.Generic;
    
    namespace 数据流中的中位数
    {
        class Program
        {
            static void Main(string[] args)
            {
                int[] num = new int[9] { 5, 2, 3, 4, 1, 6, 7, 0, 8 };
                Solution s = new Solution();
                for (int i = 0; i < num.Length; i++)        //模拟逐次从流中读出数据,取其中位数查看结果
                {
                    s.Insert(num[i]);
                    Console.WriteLine(s.GetMedian());
                }
            }
        }
        class Solution
        {
            private List<int> max = new List<int>();                //容器右边较大数所存储的堆
            private List<int> min = new List<int>();                //容器左边较小数所存储的堆
    
    
            /// <summary>
            /// 首先需要保证最大堆和最小堆能够平均分配数据,因此两个堆的数目差不能超过1.为了实现平均分配,可以在数据的总数目是偶数时把新数据插入最小堆,否则插入最大堆。
            /// </summary>
            /// <param name="num">插入的数字</param>
            public void Insert(int num)
            {
                //如果两个容器数量不平衡,则让其保持平衡,把新数据添加到max中
                if (((min.Count + max.Count) & 1) == 0)
                {
                    //新插入的数据大于最小堆的最大值,那么先把这个数据添加进最大堆,然后取出最大堆的最小值,把最小值插入最小堆min中
                    if (max.Count > 0 && num > max[0])
                    {
                        Add(max, num);
                        num = max[0];
                        max.RemoveAt(0);
                    }
                    Add(min, num);
                }
                else
                {
                    //如果要把新数据插入最大堆max,先判断新数据是否小于最小堆的最大值,如果是,那么先把新数据插入最小堆,取出最小堆的最大值,
                    //把得到的最大值插入最大堆max中
                    if (min.Count > 0 && min[min.Count - 1] > num)
                    {
                        Add(min, num);
                        num = min[min.Count - 1];
                        min.RemoveAt(min.Count - 1);
                    }
                    Add(max, num);
                }
            }
    
    
            /// <summary>
            /// 用来得到中位数,如果最大堆和最小堆的数量加起来是偶数,说明中位数得计算,那么求最大堆最小值与最小堆最大值的和的一半即可
            /// </summary>
            /// <returns>中位数</returns>
            public double GetMedian()
            {
                int size = min.Count + max.Count;
                //如果两个堆数据数目之和为奇数,说明返回最小堆的最大值即可(因为优先插入最小堆,最小堆会比最大堆多一个数)
                if ((size & 1) == 0)
                    return (double)(min[min.Count - 1] + max[0]) / 2.0;
    
    
                return (double)min[min.Count - 1];
            }
    
    
            //排好序的添加到两个堆中,都按升序排列,在调用最小堆时,则逆序调用即可
            private void Add(List<int> list, int num)
            {
                if (list.Count == 0)
                    list.Add(num);
                else
                {
                    for (int i = 0; i < list.Count; i++)
                    {
                        if (list[i] > num)
                        {
                            list.Insert(i, num);
                            return;
                        }
                    }
                    list.Add(num);
                }
            }
        }
    }

     

    展开全文
  • 中位数

    千次阅读 2013-03-19 10:23:57
    中位数(Medians)统计学名词,是指将统计总体当中的各个变量值按大小顺序排列起来,形成一个数列,处于变量... 中位数作用与算术平均数相近,也是作为所研究数据的代表值。一个等差数列或一个正态分布数列中,中

           中位数(Medians)统计学名词,是指将统计总体当中的各个变量值按大小顺序排列起来,形成一个数列,处于变量数列中间位置的变量值就称为中位数,用Me表示。当变量值的项数N为奇数时,处于中间位置的变量值即为中位数;当N为偶数时,中位数则为处于中间位置的2个变量值的平均数。

    中位数的作用

           中位数的作用与算术平均数相近,也是作为所研究数据的代表值。在一个等差数列或一个正态分布数列中,中位数就等于算术平均数。 在数列中出现了极端变量值的情况下,用中位数作为代表值要比用算术平均数更好,因为中位数不受极端变量值的影响;如果研究目的就是为了反映中间水平,当然也应该用中位数。在统计数据的处理和分析时,可结合使用中位数。

    中位数的计算

           确定中位数,必须将总体各单位的标志值按大小顺序排列,最好是编制出变量数列。

           这里有两种情况:

           1、观测数据量较小时

                对于未分组的原始资料,首先必须将标志值按大小排序。设排序的结果为:

                                         

               则中位数就可以按下面的方式确定:

                                        

               例:2、3、4、5、6、7 中位数:中间的两个数相加后除2=(4+5)/2=4.5

           2、观测数据量很大时。

                观测数据量很大时,中位数的计算开销很大,可以利用“分组资料”的方法确定中位数的近似值。

               由组距数列确定中位数,应先按的公式求出中位数所在组的位置,然后再按下限公式或上限公式确定中位数。

               下限公式:

               上限公式:

       式中:

    Me——中位数;
    L——中位数所在组下限;
    U——中位数所在组上限;
    fm——为中位数所在组的次数;
    ∑f——总次数;
    d——中位数所在组的组距;
    Sm − 1——中位数所在组以下的累计次数;
    Sm + 1——中位数所在组以上的累计次数。

    例:根据上面例表的数据,计算50名工人日加工零件数的中位数。

    解(某企业50名工人加工零件中位数计算表):


    由上表可知,中位数的位置=50/2=25,即中位数在120~125这一组,L=120,Sm − 1 = 16,U=125,Sm + 1 = 20fm = 14,d=5,根据中位数公式得:



    展开全文
  • 题目描述如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

    题目描述

    如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

    分析

    获取中位数有多种方法,但是各种方法的时间效率不一。下面是多种方法的时间复杂度的比较:有图可以知道使用AVL二叉平衡树的方法和使用最大堆最小堆的方法是总的时间复杂度最优的。但是AVL二叉平衡树没有现成的数据结构的实现,因此可以考虑java集合中的PriorityQueue优先队列(也就是堆,默认为小根堆)来实现比较高校的中位数查找。

    获取中位数的多种方法时间复杂度比较

    思路:考虑将数据序列从中间开始分为两个部分,左边部分使用大根堆表示,右边部分使用小根堆存储。每遍历一个数据,计数器count增加1,当count是偶数时,将数据插入小根堆;当count是奇数时,将数据插入大根堆。当所有数据遍历插入完成后(时间复杂度为O(logn),如果count最后为偶数,则中位数为大根堆堆顶元素和小根堆堆顶元素和的一半;如果count最后为奇数,则中位数为小根堆堆顶元素。

    牛客AC:

    import java.util.PriorityQueue;
    import java.util.Comparator;
    
    public class Solution {
    
        private int count = 0;  // 数据流中的数据个数
        // 优先队列集合实现了堆,默认实现的小根堆
        private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // 定义大根堆,更改比较方式
        private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;     // o1 - o2 则是小根堆
            }
        });
    
        public void Insert(Integer num) {
            if ((count & 1) == 0) {
                // 当数据总数为偶数时,新加入的元素,应当进入小根堆
                // (注意不是直接进入小根堆,而是经大根堆筛选后取大根堆中最大元素进入小根堆)
                // 1.新加入的元素先入到大根堆,由大根堆筛选出堆中最大的元素
                maxHeap.offer(num);
                int filteredMaxNum = maxHeap.poll();
                // 2.筛选后的【大根堆中的最大元素】进入小根堆
                minHeap.offer(filteredMaxNum);
            } else {
                // 当数据总数为奇数时,新加入的元素,应当进入大根堆
                // (注意不是直接进入大根堆,而是经小根堆筛选后取小根堆中最大元素进入大根堆)
                // 1.新加入的元素先入到小根堆,由小根堆筛选出堆中最小的元素
                minHeap.offer(num);
                int filteredMinNum = minHeap.poll();
                // 2.筛选后的【小根堆中的最小元素】进入小根堆
                maxHeap.offer(filteredMinNum);
            }
            count++;
        }
    
    
        public Double GetMedian() {
            // 数目为偶数时,中位数为小根堆堆顶元素与大根堆堆顶元素和的一半
            if ((count & 1) == 0) {
                return new Double((minHeap.peek() + maxHeap.peek())) / 2;
            } else {
                return new Double(minHeap.peek());
            }
        }
    
    }

    参考
    1. 何海涛,剑指offer名企面试官精讲典型编程题(纪念版),电子工业出版社

    展开全文
  • 具体来说,我们将以分析历史股价为例,介绍怎样从文件载入数据,以及怎样使用NumPy的基本数学和统计分析函数。这里还将学习读写文件的方法,并尝试函数式编程和NumPy线性代数运算。 第三章 常用函数 3.9 统计分析 ...
  • 题目:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有值排序之后位于中间的数值。如果数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。解题思路 ...
  • 对于未分组数据,可使用Excel的MEDIAN函数求解中位数。 对于分组数据,分为: ...假设数据在每个等级区间内均匀分布下,采用以下公式来估计组数据中位数。 看似非常简单的中位数计算,使用了实际数
  • 从海量数据中找出中位数

    千次阅读 2012-10-19 08:56:52
    关于中位数数据排序后,位置最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+
  • bfptr算法(即中位数中位数算法)

    万次阅读 多人点赞 2018-08-25 22:35:16
    BFPRT算法是解决从n个数中选择第k大或第k小的这个经典问题的著名算法,但很多人并不了解其细节。本文将首先介绍求解这个第k小数字问题的几个思路,然后重点介绍最坏情况下复杂度仍然为O(n)的BFPRT算法。 一 ...
  • 海量数据中位数

    万次阅读 2011-11-14 14:11:30
    腾讯一面问到了,用的算法导论中的Kth算法,期望...只有2G内存的pc机,一个存有10G个整数的文件,从中找到中位数,写一个算法。 http://blog.sina.com.cn/s/blog_4a8aac970100093j.html~type=v5_one&label=rela_nex
  • 利用SQL求中位数(已修复BUG)

    万次阅读 热门讨论 2019-09-18 16:48:36
    看《SQL进阶教程》,看到用 HAVING 子句进行自连接:求中位数 这一节时对于给出的SQL不是很理解。因此花了一些时间分析了一下。体会贴此博文中。 HAVING 子句进行自连接:求中位数 中位数是指将集合中的元素按照...
  • 这并不是意味着拿它相邻的单元格来替换,而是你需要寻找除了空的这个单元格,哪一行数据在其他列上的内容与存在空值的这行数据是最接近的,然后用该行的数据进行替换。这种方式较为严谨,但也比较费事。 第二种思路...
  • 学习了用R计算样本数据的平均值之后(用R计算均值),下面继续学习其他统计量。 中位数 定义: 为什么要有中位数?...我们要知道的是,均值描述并不总是可靠的或最佳的。...中位数定义为数据排序位
  • lintcode两个排序数组的中位数

    千次阅读 2017-08-31 18:41:27
    两个排序数组的中位数   描述 笔记  数据  评测 两个排序的数组A和B分别含有m和n个数,找到两个排序数组的中位数,要求时间复杂度应为O(log (m+n))。 您真实的面试中是否遇到过...
  • BFPRT(中位数中位数)算法

    千次阅读 2017-10-09 16:05:05
    BFPRT 算法又称为 “中位数中位数算法”,该算法由 Blum、Floyd、Pratt、Rivest、Tarjan 1973年提出,最坏时间复杂度为 O(n) TOP-K问题
  • 寻找两个正序数组的中位数1、问题分析2、问题解决3、总结 1、问题分析 题目链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/ 具体思路是: 1、 根据两个数组的总长度计算是否是 ...
  • 寻找两个有序数组的中位数

    千次阅读 2019-02-17 13:13:06
    请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例: A = [1, 3] B = [2] 则中位数是 2.0 A = [1, 2] B = [3, 4] 则中位数是 (2 + 3...
  • 求一个无序数组的中位数

    千次阅读 2017-08-08 23:37:29
    求一个无序数组的中位数。 如:{2,5,4,9,3,6,8,7,1}的中位数为5。 要求:不能使用排序。 暂时只考虑奇数时的情况,偶数有时会规定相邻两个数的平均数。 下面的分析都只考虑奇数的情况。 思路1:对前(n+1)/2个...
  • 一组数据中如果有特别大的数或特别小的数时,一般用中位数 一组数据比较多(20个以上),范围比较集中,一般用众数 其余情况一般还是平均数比较精确 一、联系与区别:  1、平均数是通过计算得到的,因此它会因...
  • 均值、中位数、众数是表示一组数据集中趋势的量数,下面以“1,2,3,3,5,7,7,8,9,10”数据集为例 均值,中位数,众数 Type 示例 值 说明 均值(Mean) (1+2+3+3+5+7+7+8+9+10)/10 5.5 算术平均数。求和,...
  • 请找出两个排序数组的中位数并且总的运行时间复杂度为 O(log (m+n)) 。 示例 1: nums1 = [1, 3] nums2 = [2] 中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5 这是问题,我刚...
  • 移动平均法 移动平均法是指上是对... 移动项k即为从第一项开始k每隔k项相加,然后相加所得的值除以k就得到了新的时间序列,22=5+7+10得到三项移动的平均值为7.33。有以上例子可以看出,简单的移动平均可以消除...
  • 探索性数据分析(Exploratory Data Analysis ,EDA)是对数据进行分析并得出规律的一种数据分析方法。它是一个故事,一个数据试图讲述的故事。EDA是一种利用各种工具和图形技术(如柱状图、直方图等)分析数据的方法。 ...
  • C语言计算平均数/众数/中位数

    千次阅读 2019-12-18 16:50:57
    调查数据分析(Survey data analysis)中经常需要计算平均数、中位数和众数。用函数编程计算40个输入数据(是取值1—10之间的任意整数)的平均数(Mean)、中位数(Median)和众数(Mode)。中位数指的是排列...
  • 采集获取知名招聘网站上的求职和招聘信息并通过商业智能开展职业职位供求及趋势等相关统计分析。何用MDX求解薪水中位数、四分位数(Median,Quartile)等。
  • 偏态分布的均值与中位数关系

    千次阅读 2020-04-11 18:13:31
    于是想起数据挖掘课上提到的正偏态分布中,均值大于中位数的问题。思考很久无法证明。 关于正偏态,正态和负偏态的图如下。 正偏也叫右偏,看起来好像是峰值左,怎么会叫右偏呢?按维基百科的解释是:传统...
  • 数据分析在保险销售的应用

    千次阅读 2018-08-31 16:36:19
    此部分报告是笔者曾经新人班,给新人做过的培训内容(产生一定的成效)。此,作详细记录(考虑到部分敏感词汇,故而部分内容省略)。 一、背景分析及问题提出 1.背景分析 2.问题提出 二、用到的主要工具 三...
  • 参考上面的草图:可以这样理解,(1)对于正偏态而言,数据大多分布右侧,从而也就把期望与中位数往右侧移动。(2)对于负偏态而言,数据大多分布左侧,从而也就把期望与中位数往左侧移动。 ...
  • 中位数,快速选择算法

    万次阅读 2017-07-11 15:12:56
    分析:于是此题就转化为了求中位数,关于求中位数,可以先排序,然后中间那个就是所求,但是为了体现分治的思想,同时追求更高的效率,于是本次用随机选择算法,随机选择算法和快速排序有点像。 随机选择算法求中位...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 532,408
精华内容 212,963
关键字:

中位数在数据分析中的作用