清风白茶

我们都会上岸,阳光万里,去哪里都是鲜花开放。
leetcode-最小的k个数

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. 调用库函数排序

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

img

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):
# 调整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]=11作为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] # 注意这里,单个重复的元素多余k个的情况

来感受一下这个速度!

img

2. 最后

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


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×