《剑指offer》python ： 40 最小的k个数

﹏ヽ暗。殇╰゛Y 2022-05-17 08:11 167阅读 0赞

## 题目 ##

输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8 这8个数字，则最小的4个数字是1、2、3、4。

--------------------

### 法0：(最简单的思路）整体排序后取前k个数 ###

利用python自带sorted()函数。  
复杂度为O( ***n*** log ***n***)，面试官会告诉你还有更快的算法

return sorted(tinput)[:k]

### 法1：冒泡法 ###

利用冒泡法，临近的数字两两进行比较,按照从小到大的顺序进行交换,如果前面的值比后面的大，则交换顺序。这样一趟过去后,最小的数字被交换到了第一位；然后是次小的交换到了第二位，。。。，依次直到第k个数，停止交换。返回lists的前k个数。

#   冒泡法
    def BubbleSort(lists,k):
        length = len(lists)
        for i in range(k):
            for j in range(i+1,length):
                if lists[i] > lists[j]:
                    lists[j],lists[i] = lists[i],lists[j] # 交换，冒个泡
        return lists[0:k]

### 法2：基于Partition 函数 ###

**思路：**从39题“数组中出现次数超过一半的数字”得到启发，用快排中的Partition思想。  
**操作：**  
①随机选一数为key，在partition函数中完成一轮比较的结果是，比key大的数都在其右边，比key小的数放在其左边。返回 key的index。  
②判断index与k的大小：  
如果 index > k，说明前k小的数在key左边，故需把寻找范围缩小，在key左侧找。  
如果 index < k，说明上轮partition之后，前index个数找的太少了，我们需要再往数组的后面找。

复杂度：O(***n***)  
缺点：需要修改输入的数组

def partition(lists,left,right):
        #划分函数处理部分
        key = lists[left]
        while left < right:
            while left < right and lists[right] >= key:
                right -= 1
            lists[left] = lists[right]
            while left < right and lists[left] <= key:
                left += 1
            lists[right] = lists[left]
        lists[right] = key
        return left
    def topK(lists,k):
        #划分法主要函数部分
        length = len(lists)
        left = 0
        right = length - 1
        index = partition(lists,left,right)
        while k-1!=index:
            if index > k-1:
                right = index-1
            else:
                left = index+1
            index = partition(lists,left,right) 
        return sorted(lists[0:k])

### 法3：（容器法）基于堆和红黑树 ###

**思路：**造个大小为k的容器，选出最大值max。遍历数组，比max大的值忽略掉，小的则加入容器，并丢掉旧的max，最后选出新的max。 瓶颈在于如何快速从容器中k个值中选出最大值max。这里容器的最佳选择为**堆**或**红黑树**。  
这一题应用堆排序算法复杂度只有O(nlog k)，堆是完全二叉树的一种，最大堆就是最上面的数是最大的

**操作：**该方法基于二叉树或者堆来实现，首先把数组前k个数字构建一个最大堆，然后从第k+1个数字开始遍历数组，如果遍历到的元素小于堆顶的数字，那么替换两个数字，重新构造堆，继续遍历，最后剩下的堆就是最小的k个数。  
时间复杂度：O(***n*** log ***k***)

--------------------

### 对比 ###

<table> 
 <thead> 
  <tr> 
   <th>-</th> 
   <th>整体排序法</th> 
   <th>基于Partition 函数</th> 
   <th>（容器法）基于堆和红黑树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>复杂度</td> 
   <td>O( <strong><em>n</em></strong> log <strong><em>n</em></strong>)</td> 
   <td>O(<strong><em>n</em></strong>)</td> 
   <td>O(<strong><em>n</em></strong> log <strong><em>k</em></strong>)</td> 
  </tr> 
  <tr> 
   <td>是否需要修改数组</td> 
   <td>√</td> 
   <td>√</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>适合海量数据</td> 
   <td>×</td> 
   <td>×</td> 
   <td>√</td> 
  </tr> 
 </tbody> 
</table>

对比发现，当n>>k时，容器法的优势会很明显，所以**容器法**更适合海量数据的情景，这也是互联网大厂面试官们期待的解法。

Ref:  
《剑指offer》第二版 第五章 优化时间和空间效率  
[剑指offer之最小的K个数（Python）][offer_K_Python]

[offer_K_Python]: https://blog.csdn.net/u010636181/article/details/78417977