算法：堆（优先队列）

堆（优先队列）分为最大堆和最小堆。

python实现

class HEAPQ:
	# 最小堆
    def __init__(self, l):
        self.l = l
        self.build()

    def build(self):
        n = len(self.l)
        end = n // 2
        for i in range(end, -1, -1):
            self.update(i)

    def update(self, i):
        l = self.l
        n = len(l)
        idx = i
        if 2 * i + 1 < n and l[2 * i + 1] < l[idx]:
            idx = 2 * i + 1
        if 2 * i + 2 < n and l[2 * i + 2] < l[idx]:
            idx = 2 * i + 2
        if idx != i:
            l[i], l[idx] = l[idx], l[i]
            self.update(idx)

    def push(self, x) -> int:
        l = self.l
        l.append(x)
        i = len(l)-1
        while i != 0:
            parent = (i-1) // 2
            # 父节点大于 则上浮
            if l[parent] > l[i]:
                l[parent], l[i] = l[i], l[parent]
                i = parent
            else:
                break

    def pop(self):
        l = self.l
        n = len(l)
        l[0], l[n - 1] = l[n - 1], l[0]
        t = l.pop()
        self.update(0)
        return t

    def top(self):
        return self.l[0]
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
39
40
41
42
43
44
45
46
47

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

215. 数组中的第K个最大元素

面试题 17.09. 第 k 个数

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
面试题 17.09. 第 k 个数

class Solution:
    def getKthMagicNumber(self, k: int) -> int:
        l = [1]
        ss = set()
        tt = (3,5,7)
        for i in range(1,k):
            t = heapq.heappop(l)
            for x in tt:
                if t*x not in ss:
                    heapq.heappush(l, t*x)
                    ss.add(t*x)
        return l[0]

1
2
3
4
5
6
7
8
9
10
11
12
13