ARTS-Week 4

ARTS 计划：每周至少写一道算法题，阅读并点评至少一篇英文文章，学习至少一个技术技巧，分享一篇有观点和思考的技术文章。本周的算法是在数组中找出第k大的数字，在写算法的时候同时巩固了下排序算法，并且也学习了一些Python对排序算法作出一些优化和Python库。在英文阅读中学习了如何高效代码审查并且尝试翻译全文。最后分享两个挺不错的Python面试题集合的GitHub，各持所需。

Algorithm

• 215. Kth Largest Element in an Array

在数组中找出第k大的数字，第k大表示是按排序的方式的第k个元素，而不需要去重之后的第k个不同元素。

首先想到的就是简单的排序，尝试使用 Python 自带的排序算法，先排序，后取数字。

class Solution:
    def findKthLargest(self, nums: list, k: int) -> int:
        # 排序，获取第k大的值
        nums.sort(reverse=True)
        return nums[k - 1]

事实上这样就通过了，不过速度太慢了，之后能想到的就是使用最大堆，维持堆的数量在 k 个数字，最后获取第k个数字就是所求。

class Solution:
    def findKthLargest(self, nums: list, k: int) -> int:
        # 堆，获取第n大的值
        from heapq import nlargest
        return nlargest(k, nums)[-1]

最后是采用快排的思想去找第k大的数字：

class Solution:
    def findKthLargest(self, nums: list, k: int) -> int:
        # 快速排序获取第k大的值
        def partition(left, right, pivot_index):
            pivot = nums[pivot_index]
            nums[pivot_index], nums[right] = nums[right], nums[pivot_index]

            store_index = left
            for i in range(left, right):
                if nums[i] < pivot:
                    nums[store_index], nums[i] = nums[i], nums[store_index]
                    store_index += 1

            nums[right], nums[store_index] = nums[store_index], nums[right]

            return store_index

        def select(left, right, k_smallest):
            if left == right:
                return nums[left]

            # pivot_index = random.randint(left, right)
            # 这里分区点的选点改为选中间点
            pivot_index = (left+right)//2
            pivot_index = partition(left, right, pivot_index)

            if k_smallest == pivot_index:
                return nums[k_smallest]
            elif k_smallest < pivot_index:
                return select(left, pivot_index - 1, k_smallest)
            else:
                return select(pivot_index + 1, right, k_smallest)

        return select(0, len(nums) - 1, len(nums) - k)

题目求第k大的元素，反过来说就是求第 len(nums)-k 小的元素，在获得分区点的时候，依据快排的思想，如果获得的分区点下标恰好是要求的第 len(nums)-k 小的元素，那该下标对应的值就是所求。

需要注意的是，对于中间分区点的选择其实挺重要的，这里尝试了随机的方式、取最后一位和取中间一位的方式，最后发现取中间和随机的方式速度快上一些，这可能是测试用例中有专门对取最后一位的特例，使得算法复杂度上升到 级。

其中的快排可以参考我的另一篇文章：排序算法 | Python 实现

Review

• LinkedIn’s Tips for Highly Effective Code Review

本周学习了 Linkin 的高效代码审查的文章，文章以提问题的方式逐一指出代码审查的好处以及一些注意事项，给出建议和一些见解。

也开始尝试翻译文章，下面的连接是我对该文章的翻译：

文章翻译 | LinkedIn’s Tips for Highly Effective Code Review

Tip

Python 中的一个模块 heapq

这个模块实现了堆排序算法（优先队列算法）。

这个模块实现了一个二叉树，每个父节点的值都只会小于或大于所有孩子节点（的值）。它使用了数组来实现：从零开始计数，对于所有的 k ，都有heap[k] <= heap[2*k+1] 和 heap[k] <= heap[2*k+2] 。

还有一些常用的方法：

• heapq.heappush(heap, item) 将 item 的值加入 heap 中，保持堆的不变性。
• heapq.heappop(heap) 弹出并返回 heap 的最小的元素，保持堆的不变性。如果堆为空，抛出 IndexError 。使用 heap[0] ，可以只访问最小的元素而不弹出它。
• heapq.heappushpop(heap, item) 将元素 item 放入堆中，然后弹出并返回堆 heap 中的最小元素。该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。
• heapq.heapify(x) 将列表 list x 转换成堆，原地，线性时间内。
• heapq.heapreplace(heap, item) 从堆中返回并弹出最小的元素，并将新的元素 item 加入堆中。与 heappushpop() 不同是先进行删除操作后加入新元素。
• heapq.merge( *iterables，key = None，reverse = False ) 将多个列表合并，并进行堆调整，返回的是合并后的列表的迭代器。
• heapq.nlargest(n，iterable，key = None ) 返回一个列表，其中包含 iterable 定义的数据集中的 n个 最大元素 ，即返回列表中最大的n个值。

参考：查找最大或最小的N个元素

• heapq.nsmallest(n，iterable，key = None ) 返回一个列表，其中包含 iterable 定义的数据集中的 n个 最小元素 ，即返回列表汇总最小的n个元素。

Share

分享几个Python面试题集合的网址，各持所需，不管是去面试还是出面试题，亦或是取长补短，都可以学习看看。

• 关于Python的面试题
• python的面试题
• Python面试题汇总