BM 46 最小的K个数

url：牛客 BM46

考察知识点：堆、快速排序

有了堆这把锤子之后眼里就多了最大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
import heapq
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        if len(input) == 0 or k == 0:
            return []

        heap = []
        for i in range(k):
            heapq.heappush(heap, -input[i])
        for i in range(k, len(input)):
            if input[i] < -1 * heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap, -input[i])

        # 返回时将结果转换为正值
        return [-val for val in heap]

当然这个还可以用快速排序实现，之后我可能再像堆一样给快速排序写个单独的文章，梳理一下这个最流行的排序算法。

BM 47 寻找第K大

url：牛客 BM47

考察知识点：堆、快速排序

光看要求，这简直就是给堆定制的题目。用容量为K的最小堆过一遍数组，之后根节点就是第K大了！尽管题目要求需要快速排序思路实现，这个下次再写。先用最小堆实现一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import heapq
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        heap = a[:K]
        heapq.heapify(heap)

        for i in range(K, len(a)):
            if a[i] > heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap, a[i])

        return heap[0]