题目要求:输入整数数组 arr
,找出其中最小的 k
个数。 例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。题目地址点这里 .****
1.解题方法 说明本文代码全部是使用python3。
本文给出三种解决方案:
调用库函数sorted
直接排序,比下面的所有方法都要快🤔🤔🤔🤔 最大堆(前K小), 维持一个大小为K的最大堆复杂度:O(NlogkNlogk) 题目给出了数组的最大大小,可以使用计数排序,复杂度:O(N)O(N) 还有一种方法是快排。
1. 调用库函数排序 这个是最最最简单,一行代码就搞定了。这???还挺快??
1 2 3 class Solution : def getLeastNumbers (self, arr, k ): return sorted (arr)[:k]
2. 最大堆 使用给定数组的前k个数建立一个最大堆,接下来只需要把数组中剩下的数依次和堆顶的数比较,比堆顶小的数入堆,比堆顶大的舍弃。这样遍历完整个数组后,这时最大堆里的数就是前k个小的数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution : def getLeastNumbers (self, arr, k ): 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个数就可以了。
1 2 3 4 5 6 7 8 9 10 11 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]
来感受一下这个速度!
2. 最后 这个题,其实还有很多的解法,等有时间再写写快排吧。第三个计数排序里,是有个bug的,如果给定的数组里有负数的话,那这个方法就行不通了。