Python数据结构与算法-在M个数中找K个最小的数

题目:输入M个数,从中找到K个最小的数

比如输入10,-9,0,100,90,1,4,-9;找到最小的3个数为:-9,-9,0

1这道题最坏的办法是对M个数进行排序,排序算法最好的时间复杂度是o(mlogm)

2 第二种办法,是对其中的K个数进行排序,时间复杂度是o(m*k*logk),这要对比m和k*logk的大小,看哪个办法更优

3 对于第二种方法的一个优化是,不需要对K个数进行排序,只需要要到这K个数中最大的数A,然后下一个数跟A对比,比A大则不要,比A小则入选,如此循环;时间复杂度是o(m*k)

4 最后一种是对方法3的一个优化,在找数组K个数中最大数时,最好的时间复杂度是用大根堆的方式,时间复杂度是logk,整体的时间复杂度是o(m*logk)。

代码思路:

对前k个数,进行建立大根堆;建立大根堆时,从(k-1)/2的位置开始向上进行调整;

然后对后面m-k个数据,一个数据一个数据的与堆的根节点进行大小对比,比根节点小的,用这个值替换根节点,然后在从根节点对堆进行调整。

这样最后堆里的内容就是要输出的内容

下面是第四种方式的代码:

'''
查找最小的k个元素
题目:输入n个整数,输出其中最小的k个。
例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4
'''

def adjustHeap(heap, page):
    '''
    堆的调整
    param:heap是堆的数组,page是需要调整的节点
    '''
    temp = page
    #找page和page左节点和右节点三个点中,最大的一个点
    if 2*temp+1 < len(heap):
        if heap[2*temp+1] > heap[temp]:
           temp = 2*temp+1
    if 2*temp+2 < len(heap):
        if heap[2*temp+2] > heap[temp]:
            temp = 2*temp+2
    #调整用最大的节点作为根节点,然后在对调整后的节点继续做调整
    if temp != page:
        temp_data = heap[page]
        heap[page] = heap[temp]
        heap[temp] = temp_data
        adjustHeap(heap, temp)


if __name__ == "__main__":   
    m = [10,-9,0,100,90,1,4,-9]
    k = 7
    heap = []
    len_m = len(m)
    #对异常输入做返回
    if k <=0 or len_m<=0 or k > len_m:
        print None
    #如果长度相当直接返回
    else:
        if k==len_m:
            print m

        else:
            #否则先对前k个节点,从后向前调整
            heap = m[:k]
            index = (k-1)/2
            while index >= 0:
                adjustHeap(heap, index)
                index = index - 1
            tail = k-len_m
            m = m[tail:]
            #然后在用后面的数据跟根节点进行大小比较,如果比根节点小,则替换根节点,在从上向下做调整
            for i in m:
                if i < heap[0]:
                    heap[0] = i
                    adjustHeap(heap, 0)
            print heap

输出:[90, 10, 1, -9, -9, 0, 4]

原文发布于微信公众号 - 玄魂工作室(xuanhun521)

原文发表时间:2018-08-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习思考者

一文搞懂算法的时间复杂度与空间复杂度

一 时间复杂度的概念   一般情况下,算法的基本操作重复执行的次数是模块n的某一函数f(n),因此,算法的时间复杂度记做 T(n) = O(f(n))。 随着模...

7188
来自专栏HTML5学堂

游戏开发 - Math对象相关知识讲解

前几期小编给大家总结了JavaScript的基础知识,为我们后期深入学习JS打下了一定的基础。在后面的几期文章当中我们要来进行JS小游戏的开发,但是开发小游戏的...

29210
来自专栏塔奇克马敲代码

不相交集类

3395
来自专栏chenjx85的技术专栏

leetcode-566-Reshape the Matrix

1987
来自专栏数据小魔方

左右用R右手Python9——字符串合并与拆分

在文本处理和数据清洗阶段,对字符串或者字符型变量进行分割、提取或者合并虽然谈不上什么高频需求,但是往往也对很重要的。 接下来跟大家大致盘点一下在R语言与Pyh...

3465
来自专栏编码前线

布隆过滤器(Bloom Filter)详解

直观的说,bloom算法类似一个hash set,用来判断某个元素(key)是否在某个集合中。 和一般的hash set不同的是,这个算法无需存储key的值,对...

2994
来自专栏海天一树

小朋友学算法(6):求幂pow函数的四种实现方式

在math.h中,声明了一个函数pow(x, n),用于求x的n次方。 假如咱们不调用math.h中的pow函数,如何实现求x ^ n的算法呢?

1562
来自专栏阮一峰的网络日志

Reduce 和 Transduce 的含义

学习函数式编程,必须掌握很多术语,否则根本看不懂文档。 本文介绍两个基本术语:reduce和transduce。它们非常重要,也非常有用。 ? 一、reduce...

2817
来自专栏前端儿

A+B Problem(V)

做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

831
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2232

扫码关注云+社区

领取腾讯云代金券