|
1 | 1 | ================================
|
2 |
| -1.4 查找最大或最小的N个元素 |
| 2 | +1.4 查找最大或最小的 N 个元素 |
3 | 3 | ================================
|
4 | 4 |
|
5 | 5 | ----------
|
6 | 6 | 问题
|
7 | 7 | ----------
|
8 |
| -怎样从一个集合中获得最大或者最小的N个元素列表? |
| 8 | +怎样从一个集合中获得最大或者最小的 N 个元素列表? |
9 | 9 |
|
10 | 10 | ----------
|
11 | 11 | 解决方案
|
12 | 12 | ----------
|
13 |
| -heapq模块有两个函数:``nlargest()`` 和 ``nsmallest()`` 可以完美解决这个问题。 |
| 13 | +heapq 模块有两个函数:``nlargest()`` 和 ``nsmallest()`` 可以完美解决这个问题。 |
14 | 14 |
|
15 | 15 | .. code-block:: python
|
16 | 16 |
|
@@ -39,37 +39,38 @@ heapq模块有两个函数:``nlargest()`` 和 ``nsmallest()`` 可以完美解
|
39 | 39 | ----------
|
40 | 40 | 讨论
|
41 | 41 | ----------
|
42 |
| -如果你想在一个集合中查找最小或最大的N个元素,并且N小于集合元素数量,那么这些函数提供了很好的性能。 |
| 42 | +如果你想在一个集合中查找最小或最大的 N 个元素,并且 N 小于集合元素数量,那么这些函数提供了很好的性能。 |
43 | 43 | 因为在底层实现里面,首先会先将集合数据进行堆排序后放入一个列表中:
|
44 | 44 |
|
45 | 45 | .. code-block:: python
|
46 | 46 |
|
47 | 47 | >>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
|
48 | 48 | >>> import heapq
|
49 |
| - >>> heapq.heapify(nums) |
| 49 | + >>> heap = list(nums) |
| 50 | + >>> heapq.heapify(heap) |
50 | 51 | >>> nums
|
51 | 52 | [-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]
|
52 | 53 | >>>
|
53 | 54 |
|
54 | 55 | 堆数据结构最重要的特征是 ``heap[0]`` 永远是最小的元素。并且剩余的元素可以很容易的通过调用 ``heapq.heappop()`` 方法得到,
|
55 |
| -该方法会先将第一个元素弹出来,然后用下一个最小的元素来取代被弹出元素(这种操作时间复杂度仅仅是O(log N),N是堆大小)。 |
56 |
| -比如,如果想要查找最小的3个元素,你可以这样做: |
| 56 | +该方法会先将第一个元素弹出来,然后用下一个最小的元素来取代被弹出元素(这种操作时间复杂度仅仅是 O(log N),N 是堆大小)。 |
| 57 | +比如,如果想要查找最小的 3 个元素,你可以这样做: |
57 | 58 |
|
58 | 59 | .. code-block:: python
|
59 | 60 |
|
60 |
| - >>> heapq.heappop(nums) |
| 61 | + >>> heapq.heappop(heap) |
61 | 62 | -4
|
62 |
| - >>> heapq.heappop(nums) |
| 63 | + >>> heapq.heappop(heap) |
63 | 64 | 1
|
64 |
| - >>> heapq.heappop(nums) |
| 65 | + >>> heapq.heappop(heap) |
65 | 66 | 2
|
66 | 67 |
|
67 | 68 | 当要查找的元素个数相对比较小的时候,函数 ``nlargest()`` 和 ``nsmallest()`` 是很合适的。
|
68 |
| -如果你仅仅想查找唯一的最小或最大(N=1)的元素的话,那么使用 ``min()`` 和 ``max()`` 函数会更快些。 |
69 |
| -类似的,如果N的大小和集合大小接近的时候,通常先排序这个集合然后再使用切片操作会更快点 |
70 |
| -( ``sorted(items)[:N]`` 或者是 ``sorted(items)[-N:]`` )。 |
| 69 | +如果你仅仅想查找唯一的最小或最大(N=1)的元素的话,那么使用 ``min()`` 和 ``max()`` 函数会更快些。 |
| 70 | +类似的,如果 N 的大小和集合大小接近的时候,通常先排序这个集合然后再使用切片操作会更快点 |
| 71 | +( ``sorted(items)[:N]`` 或者是 ``sorted(items)[-N:]`` )。 |
71 | 72 | 需要在正确场合使用函数 ``nlargest()`` 和 ``nsmallest()`` 才能发挥它们的优势
|
72 |
| -(如果N快接近集合大小了,那么使用排序操作会更好些)。 |
| 73 | +(如果 N 快接近集合大小了,那么使用排序操作会更好些)。 |
73 | 74 |
|
74 | 75 | 尽管你没有必要一定使用这里的方法,但是堆数据结构的实现是一个很有趣并且值得你深入学习的东西。
|
75 | 76 | 基本上只要是数据结构和算法书籍里面都会有提及到。
|
|
0 commit comments