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

大梦三千秋 2020/6/30 13:26:27

215. 数组中的第K个最大元素 题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/kth-largest-element-in-an-array 题目 在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 示例 1: 输入…

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


题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/kth-largest-element-in-an-array

题目


在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

  • 你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

解题思路


思路:优先队列

在本题当中,我们可以使用基于堆,实现优先排列。题目要我们求第 k 个最大元素,那么建立一个最大堆,实现堆有序,做 k-1 次删除操作之后,堆顶的元素就是答案。在 Python 当中,也有相应的 API 可以直接使用。这里先不借助 API,单独实现堆。

具体算法的设计(简单步骤如下):

  • 首先构建最大堆,将数组元素存入二叉树,构建完全二叉树;
  • 实现堆有序;
  • 删除 k-1 次根节点(堆顶元素),注意恢复堆的有序性。

以示例 1 为例:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

具体的过程可见如下图解(以示例 1 为例):

图解

具体的实现代码如下。

代码实现


from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap_size = len(nums)
        self.build_max_heap(nums, heap_size)

        for i in range(len(nums)-1, len(nums)-k, -1):
            nums[0], nums[i] = nums[i], nums[0]
            heap_size -= 1
            self.max_heapify(nums, 0, heap_size)
        return nums[0]

    def build_max_heap(self, nums, heap_size):
        for i in range(heap_size // 2, -1, -1):
            self.max_heapify(nums, i, heap_size)


    def max_heapify(self, nums, i, heap_size):
        left = i * 2 + 1
        right = i * 2 + 2
        largest = i
        if left < heap_size and nums[left] > nums[largest]:
            largest = left
        if right < heap_size and nums[right] > nums[largest]:
            largest = right
        if (largest != i):
            nums[i], nums[largest] = nums[largest], nums[i]
            self.max_heapify(nums, largest, heap_size)

实现结果


实现结果

总结


  • 题目要求第 k 个最大的元素。那么可以建立一个最大堆,实现堆排序,删除 k - 1 个元素(恢复堆有序),此时堆顶元素就是答案。在这里不使用 api,尝试自行实现堆。
  • 具体的算法如下:
    • 构建最大堆,将数组元素存入堆中,构建完全二叉树
    • 实现堆有序;
    • 删除 k - 1 个元素(要注意恢复堆有序),此时堆顶就是要求的答案。

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[LeetCode 215. 数组中的第K个最大元素 | Python]http://www.zyiz.net/tech/detail-141586.html

上一篇:Python 实现·数据结构与算法之单向循环链表

下一篇:Python 中的元类到底是什么?这篇恐怕是最清楚的了

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程