leetcode-最小的k个数

题目要求：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。题目地址点这里.****

1.解题方法

说明本文代码全部是使用python3。

本文给出三种解决方案：

1. 调用库函数sorted直接排序，比下面的所有方法都要快🤔🤔🤔🤔
2. 最大堆(前K小), 维持一个大小为K的最大堆复杂度:O(NlogkNlogk)
3. 题目给出了数组的最大大小，可以使用计数排序，复杂度:O(N)O(N)

还有一种方法是快排。

1. 调用库函数排序

这个是最最最简单，一行代码就搞定了。这？？？还挺快？？

class Solution:
    def getLeastNumbers(self, arr, k):
        return sorted(arr)[:k]

2. 最大堆

使用给定数组的前k个数建立一个最大堆，接下来只需要把数组中剩下的数依次和堆顶的数比较，比堆顶小的数入堆，比堆顶大的舍弃。这样遍历完整个数组后，这时最大堆里的数就是前k个小的数。

class Solution:
    def getLeastNumbers(self, arr, k):
				# 调整index指向节点的堆序
        def ajust(index):
            while index*2 + 1 <= max_index:
                l_index = index*2 + 1		# 左节点
                r_index = l_index + 1		# 有节点
                if r_index > max_index:
                    if arr_k[index] < arr_k[l_index]:
                        arr_k[index], arr_k[l_index] = arr_k[l_index], arr_k[index]
                    index = l_index
                else:
                    if arr_k[l_index] > arr_k[r_index] and arr_k[index] < arr_k[l_index]:
                        arr_k[index], arr_k[l_index] = arr_k[l_index], arr_k[index]
                        index = l_index
                    elif arr_k[index] < arr_k[r_index]:
                        arr_k[index], arr_k[r_index] = arr_k[r_index], arr_k[index]
                        index = r_index
                    else:
                        break
        if k == 0:
            return []
          
        arr_k = arr[:k]
        max_index = k - 1
        index = int((max_index - 1) / 2)
        # 建立堆
        while index >= 0:
            ajust(index)
            index -= 1
        # 遍历数组
        for i in arr[k:]:
            if i < arr_k[0]:
                arr_k[0] = i
                ajust(0)

        res = sorted(arr_k)
        return res

3.计数排序

举个栗子，给一个数组arr = [0,0,1,3,4]. 我们创建一个新的数组大小为5nums = [0]*5, 使用arr中数组的值作为nums数组中的下标，并将值做加一处理。例如arr[2]=1将1作为nums的下标，得到nums[1]=1. 在遍历一遍数组arr后，取nums数组中的前k个数就可以了。

class Solution:
    def getLeastNumbers(self, arr, k):
        nums = [0]*10000
        for i in arr:
            nums[i] += 1
        res = []
        i = 0
        while len(res) < k:
            res += [i]*nums[i]
            i += 1
        return res[:k]	# 注意这里，单个重复的元素多余k个的情况

来感受一下这个速度！

2. 最后

这个题，其实还有很多的解法，等有时间再写写快排吧。第三个计数排序里，是有个bug的，如果给定的数组里有负数的话，那这个方法就行不通了。