面试题40:最小(大)的K个数

剑指offer40题,同时这也是面试高发题目

2019.4 蚂蚁金服问道:求1000万个数据中的前K个数。

思路:

1.直接上排序算法,然后我们就取排好顺序的前K个即可。但是单考虑快排,时间复杂度也要O(nlog(n))。这时候我们要对所有数据排序,显然随着数据量的增加,复杂度也是激增的。

2.采用时间复杂度为O(n),这时可以考虑我们之前做过的求第K大的数字。引入partition函数。

3.剑指offer上提供了一种思路:创建一个大小为K的容器,将原数据的前k个放进去,剩下的数据每个都与容器K中的最大值比较,若小于容器中的最大值,就交换。那个这个数据容器用二叉树来试下,最大值通过最大堆获得。

面试题40:最小(大)的K个数

这一题应用堆排序算法复杂度只有O(nlog k),堆是完全二叉树的一种,最大堆就是最上面的数是最大的;该方法基于二叉树或者堆来实现,首先把数组前k个数字构建一个最大堆,然后从第k+1个数字开始遍历数组,如果遍历到的元素小于堆顶的数字,那么久将换两个数字,重新构造堆,继续遍历,最后剩下的堆就是最小的k个数,时间复杂度O(nlog k)。

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        import heapq
        if tinput==None or len(tinput)<k or len(tinput)<0 or k<=0:
            return []
        
        return heapq.nsmallest(k,tinput)

  

上一篇:05 .NET CORE 2.2 使用OCELOT -- NLog


下一篇:各种排序的复杂度