精华内容
下载资源
问答
  • 面试题之二叉搜索中位数
    千次阅读
    2009-10-11 17:30:00

    这个问题不算是很常见的问题,基本上在中文的论坛社区没有看到过,遇见这个是因为偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的,题目如下:


    Given a BST (Binary search Tree) how will you find median in that?
     
    Constraints:
     
    * No extra memory.
    * Function should be reentrant (No static, global variables allowed.)
    * Median for even no of nodes will be the average of 2 middle elements and for odd no of terms will be middle element only.
    * Algorithm should be efficient in terms of complexity. 


    中文不需要赘述了,就是二叉搜索树如何高效地找到中位数,不希望申请内存,不要static/global的变量来实现。

    第一反应就是中序遍历就是排序了,但是如果要计数的话,我们需要一个额外的变量,这样恐怕需要或是静态或者全局变量了,故不可以用。但是我们其他很多次都碰到了那样类似的问题,如何把一个二叉树原地转化成双向链表,那时候还有点觉得题目没意思,没啥用处。但是在这里,作用得以体现。假如有形如

     

                                                10
                                              /    /
                                            6       14
                                          /  /     /  /
                                        4     8  12    16

    的二叉树转化成了4=6=8=10=12=14=16这样一个双链表,那后面的问题就变成了如何在4=6=8=10=12=14=16里面找到中间节点了,这对于我们习惯了2个快慢指针追赶的小朋友来说不算问题了。

    下面就是写的一个实现:

    说实话这样的题目还是比较喜欢的,考到了很多的概念和想法,

    a.中序遍历

    b.BST转化成DLL

    c.寻找链表的中间节点

    如果任何一个问题割裂开了问, 都是比较容易解决的。困难就在于如何用已知的办法组合地解决未知的问题,发人深思,余是以记之。

     

    更多相关内容
  • 从数据流中获取中位数

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

    需求描述

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

    需求分析

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

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

    千次阅读 2015-09-05 22:47:48
    序列中的中位数

    一个随机序列,找出序列的中位数,当序列个数为奇数时,为中间位置上的数字;当序列为偶数时,为中间两个数字的平均值。
    这种题有很多种做法,比较有代表性的由:
    1、partition法
    利用快排关键字的查找方法
    a.随机选取一个关键字key,将序列二分;
    b.若关键字的下标大于N/2,则继续对序列的左半部分执行partition;
    c.若关键字的下标小于N/2,则继续对序列的左半部分执行partition;
    d.若关键字的下标等于N/2,则返回key。

    这种算法:partition的时间复杂度为O(n),获取中位数的时间复杂度为O(1)。

    2、利用平衡二叉查找树
    没读取一个数字,将数字插入到二叉树中,并调整二叉树的平衡性。最后根节点就是想要的中位数。

    构建平衡二叉查找树的算法时间复杂度为O(logn),取出中位数的时间复杂度为O(n)。但是调整平衡二叉查找树算法实现比较复杂。

    3.利用堆
    原理分析:中位数无非就是将序列分为两个部分,左边的部分都小于中位数,右边的序列都大于中位数。这比较符合堆的特性(看看数据结构在算法中的重要性,选择好的数据结构能够让算法事半功倍)。可以将序列分成两个部分,左边的部分够着大根堆,右边的部分构造小根堆。

    具体实现细节:
    a.如果堆中元素的个数为偶数时,将新数字插入小根堆中(插入后堆元素的个数为奇数,此时结束插入,返回小根堆堆顶元素);如果堆中的元素个数为奇数时,将新数字插入大根堆中(插入后堆元素的个数为偶数,此时结束插入,返回两堆堆顶元素的均值)。
    b.若插入小根堆的元素大于大根堆堆顶的元素,说明新元素位于序列的右半部分,应当插入大根堆。而此时大根堆堆顶元素应当位于左半序列(小顶堆)中,因此需要将大根堆堆顶元素插入小根堆。若插入若插入小顶堆的元素不大于大顶堆堆顶的元素,则直接插入小根堆。
    c.同理,向大根堆插入元素时也有如上考虑。

    调整堆的时间复杂度为O(logn),取中位数的时间复杂度为O(1)。
    算法实现:

    template <typename T>
    class Solution {
    public:
        vector<T> minHeap;
        vector<T> maxHeap;
        void Insert(T num)
        {
            //判断数据插入的堆
            //奇数时插入大顶堆,偶数时插入小顶堆
            if((minHeap.size()+maxHeap.size())&0x01){
                if(minHeap.size() > 0 && minHeap[0] < num){
                    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>());
    
            }
            else{
                if(maxHeap.size() > 0&& maxHeap[0] > num){
                    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>());
            }
        }
    
        T GetMedian()
        { 
            int size = minHeap.size() + maxHeap.size();
            if(size <= 0) return -1;
            double result=0.0;
            if(size & 0x01) result = minHeap[0];
            else result = (minHeap[0]+maxHeap[0])/2;
    
            return result;
    
        }
    
    };
    展开全文
  • 数据流中的中位数

    千次阅读 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);
                }
            }
        }
    }

     

    展开全文
  • 在大规模数据处理,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个,或者从海量数据中找出最大的前k个,这类问题通常被称为top K问题。例如,在搜索引擎,统计搜索最热门的10个查询词;在歌曲...
  • 数据结构和算法——kd

    万次阅读 多人点赞 2017-02-02 11:31:02
    在kd的构建过程中,为了防止出现只有左子树或者只有右子的情况出现,通常对于每一个节点,选择样本中的中位数作为切分点。这样构建出来的kd时平衡的。 在李航的《统计机器学习》P41中有提到:平衡的kd...
  • 通过key的hash值计算出需要存放在哈希表的数组位置index 默认初始化容量大小为0,第一次调用put真正给默认大小16,每次扩容oldCap << 1即原来容量的2倍 常用的API方法put(key,value)/get(k
  • 决策常见的算法有ID3 C4.5 CART,这里只简述一下,不做详细介绍。因为了解了决策的概念,再看这几个算法,特别简单。重点介绍三者的关系。
  • 方法一、先拿10000个建堆,然后一次添加剩余元素,如果大于堆顶的(10000最小的),将这个替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆的10000个就是所需的最大的10000个。...
  • 数据结构和算法-2-3-4

    千次阅读 2018-06-16 23:46:47
    1、2-3-4介绍2-3-4每个节点最多有四个字节点和三个数据项,名字 2,3,4 的数字含义是指一个节点可能含有的子节点的个数。对于非叶节点有三种可能的情况: ①、有一个数据项的节点总是有两个子节点; ②、有二...
  • 一旦入坑,你会发现这个数列相当有意思,能够应用于很多看起来特别复杂的计算场景,当然,并能将之迎刃而解。 wikipedia定义:卡塔兰是组合数学一个常在各种计数问题出现的数列。以比利时的数学家欧仁·查理...
  • 这道题的思路是,先拿10000个建堆,然后一次添加剩余元素,如果大于堆顶的(10000最小的),将这个替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆的10000个就是所需的最大的10000个。...
  • 从2-3到红黑,B/B+/B*,唉!

    千次阅读 2018-07-24 09:08:31
    又跟人讨论起了红黑…于是就又扯到了2-3,顺便再聊一聊B… 二叉树就是2; 三叉就是2-3; 四叉就是2-3-4; 五叉就是2-3-4-5; … NNN叉就是2-3-4-…NNN; 唉… 其实,所谓的数据...
  • 快乐学算法之:字典Trie

    千次阅读 2020-11-09 09:58:22
    字典的英文名叫做Trie,取自retrieval,也就是检索的意思。它是一种特殊的树状结构,可以进行快速的字符插入和字符串搜索,特别适用于文本搜索和词频统计等应用方面。 本文将会详细介绍字典Trie的特性。
  • 为什么MySQL数据库索引选择使用B+

    万次阅读 多人点赞 2018-03-05 21:19:57
    在进一步分析为什么MySQL数据库索引选择使用B+之前,我相信很多小伙伴对数据结构还是有些许模糊的,因此我们由浅入深一步步探讨的演进过程,在一步步引出B以及为什么MySQL数据库索引选择使用B+!...
  • 决策- 随机森林/GBDT/XGBoost

    千次阅读 2021-10-22 22:41:24
    随机森林 单颗决策缺点:易过拟合的缺点 传统机器学习处理过拟合通常采用集成学习 (投票) ...对于回归问题,由预测值的均值决定最终预测结果 随机森林的随机性 1、每棵的训练
  • B--B+原理及操作(插入,删除)

    千次阅读 多人点赞 2019-07-29 14:18:31
    2-3:是一种路查找:2和3的意思就是2-3包含两种结点 (1)2结点包含一个元素和两个孩子(或者没有孩子)。 左子树包含结点的元素值小于该结点的元素值,右子包含的结点的元素值大于该结点的元素值...
  • 集成方法:渐进梯度回归GBRT(迭代决策

    万次阅读 多人点赞 2017-03-08 11:29:52
    http://blog.csdn.net/pipisorry/article/details/60776803单决策C4.5由于功能太简单,并且非常容易出现过拟合的现象,于是引申出了许多变种决策,就是将单决策进行模型组合,形成决策,比较典型的就是...
  • 决策算法(CART分类和回归

    千次阅读 2019-05-27 13:53:21
    决策--CART模型 上一章节介绍了决策的ID3、C4.5算法相应的原理及算法优缺点已经介绍,本章主要讲解CART的原理及相较于ID3、C4.5算法的改进。 1、CART:可以解决分类和回归问题 2、分裂节点的选择: ...
  • 虽然今天不是植树节,但是我今天想种树。 文章目录,什么是?二叉树定义二叉树的创建二叉树的前后序遍历前序遍历:中序遍历后序遍历...是我们计算机非常重要的一种数据结构,同时使用这种数据结构,可以..
  • java 实现简单圣诞的示例代码(圣诞节快乐)代码如下:@Testpublic void shengdanshu(){//叶子层int level = 10;//根层int rootLevel = 2;int spaceNum = level - 1;//画叶子// 为什么从1开始 不管了就是任性for ...
  • 今天在做表格数据统计时,...很多小数,如:3.1 + 2 = 5.100000000001 //直接转化 var val = Number(value) + Number(item); if(!isNaN(parseFloat(val))) { val = val.toFixed(2); } //直接通过方法转化
  • 【数据结构】数据结构常用的

    万次阅读 多人点赞 2016-07-31 21:29:17
    声明:本文汇总了数据结构一些常用的,主要内容来自《数据结构(严蔚敏版)》和《算法导论》这两本教材。本文主要归纳出数据结构常见的的概念与简单的性质,并未给出具体的操作,如插入、删除、查找等。1、...
  • 二叉查找(Binary Search Tree),也称二叉搜索、有序二叉树(ordered binary tree),排序二叉树(orted binary tree),是指一棵空或者具有下列性质的二叉树: 若任意节点的左子树不空,则左子树上所有节点...
  • 直接得出: 根据数组建立平衡二叉搜索 java整体打印二叉树 判断平衡二叉树 判断完全二叉树 判断二叉搜索 二叉搜索实现 堆的简单实现 堆应用例题三连 一个数据流中,随时可以取得中位数。 金条 项目最大收益...
  • Merkle Patricia Tree (MPT) 详解

    万次阅读 2019-05-17 21:10:58
     Merkle Patricia Tree(简称MPT,实际上是一种trie前缀)是以太坊的一种加密认证的数据结构,可以用来存储所有的(key,value)对。以太坊区块的头部包括一个区块头,一个交易的列表和一个uncle区块的列表。在...
  • 红黑和B的区别--2019年面试题目

    千次阅读 2019-04-20 09:56:21
    背景:这几天在看《高性能Mysql》,在看到创建高性能的索引,书上说mysql的存储引擎InnoDB采用的索引类型是B+Tree,那么,大家有没有产生这样一个疑问,对于数据索引,为什么要使用B+Tree这种数据结构,和其它相比,它能...
  • 前言前几天看到了一道简单的面试题,从5个数字中找出所有每位数字都不同的三位数的数量并且一一输出。从数学上来讲,算出数量比较简单,只是一个排列的计算。比如这道题的计算方法就是P(5,3) = 60。输出的过程也比较...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 198,931
精华内容 79,572
关键字:

很多树的中位数怎么找