算法思想: 1000亿个数自然不能全部读入内存,分部分处理。算法如下:
1.读入前100个数直接创建二叉排序树。 2.依次读入以后的数,读入时与排序树中最小的做比较。 2.1如果读入的数小于最小值,读下一个。 2.2如果读入的数大于最小值,将它插入到二叉排序树,并删除最小节点。 3.重复步骤2,直到读完所有数。 4.中序遍历二叉树输出。
空间复杂度:100个数。 时间复杂度:O(N)次比较。
本文共 246 字,大约阅读时间需要 1 分钟。
算法思想: 1000亿个数自然不能全部读入内存,分部分处理。算法如下:
1.读入前100个数直接创建二叉排序树。 2.依次读入以后的数,读入时与排序树中最小的做比较。 2.1如果读入的数小于最小值,读下一个。 2.2如果读入的数大于最小值,将它插入到二叉排序树,并删除最小节点。 3.重复步骤2,直到读完所有数。 4.中序遍历二叉树输出。
空间复杂度:100个数。 时间复杂度:O(N)次比较。
转载于:https://my.oschina.net/vincent67/blog/170801