系列索引：菜菜的刷题日记 | 被LeetCode用Python狂虐的那段日子
菜鸡的修仙之路——2022/1/17
这两天虽然没写题解博客不过每天一道依然没有断，只是写的简单题有时候觉得没写的必要。
文章目录
- 【题目】
- 【我的代码】
- 【参考代码1】暴力法
- 【参考代码2】堆排序
- 【参考代码3】快速排序
- 【思考】
【题目】
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
- 标签：数组、堆排序
- 难度：中等
python">示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
题目链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
【我的代码】
这效率真是。。Python在算法方面本身就不如c那么高效，加之我的水平不高，所以还是得多看看大佬们的代码学习学习，不过直接用sort这种就有点太那啥了吧 /wul
主要是选择排序的思想。
python">class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
for i in range(len(nums)-1, len(nums)-1-k, -1):
m = i
for j in range(i-1, -1, -1):
if nums[j] > nums[m]:
m = j
if m != i:
nums[i], nums[m] = nums[m], nums[i]
return nums[-k]
【参考代码1】暴力法
直接sort排序，不得不说这效率比我写的高多了。
简单两行直接完事，NB（虽然锻炼不了数据结构等知识）我要是面试写这会不会…
python">class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums.sort()
return nums[-k]
【参考代码2】堆排序
升序堆排序的思路如下：
-
先建立
大顶堆 -
让堆顶最大元素与最后一个交换，然后调整第一个元素到倒数第二个元素，这一步获取最大值
-
再交换堆顶元素与倒数第二个元素，然后调整第一个元素到倒数第三个元素，这一步获取第二大值
-
以此类推，直到最后一个元素交换之后完毕。
这道题我们只需进行 1 次建立大顶堆， k-1 次调整即可得到第 k 大的数。
时间复杂度：O(n2)
python">class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# 调整为大顶堆
def heapify(nums, index, end):
left = index * 2 + 1
right = left + 1
while left <= end:
# 当前节点为非叶子节点
max_index = index
if nums[left] > nums[max_index]:
max_index = left
if right <= end and nums[right] > nums[max_index]:
max_index = right
if index == max_index:
# 如果不用交换，则说明已经交换结束
break
nums[index], nums[max_index] = nums[max_index], nums[index]
# 继续调整子树
index = max_index
left = index * 2 + 1
right = left + 1
# 初始化大顶堆
def buildMaxHeap(nums):
size = len(nums)
# (size-2) // 2 是最后一个非叶节点，叶节点不用调整
for i in range((size - 2) // 2, -1, -1):
heapify(nums, i, size - 1)
return nums
buildMaxHeap(nums)
size = len(nums)
for i in range(k-1):
nums[0], nums[size-i-1] = nums[size-i-1], nums[0]
heapify(nums, 0, size-i-2)
return nums[0]
【参考代码3】快速排序
快速排序每次调整，都会确定一个元素的最终位置，且以该元素为界限，将数组分成了两个数组，前一个数组元素都比该元素小，后一个元素都比该元素大。
这样，只要某次划分的元素恰好是第 k 个下标就找到了答案。并且我们只需关注 k 元素所在区间的排序情况，与 k 元素无关的区间排序都可以忽略。这样进一步减少了执行步骤。
python">import random
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def randomPartition(nums, low, high):
i = random.randint(low, high)
nums[i], nums[high] = nums[high], nums[i]
return partition(nums, low, high)
def partition(nums, low, high):
x = nums[high]
i = low-1
for j in range(low, high):
if nums[j] <= nums[high]:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i+1], nums[high] = nums[high], nums[i+1]
return i+1
def quickSort(nums, low, high, k):
n = len(nums)
if low < high:
pi = randomPartition(nums, low, high)
if pi == n-k:
return nums[len(nums)-k]
if pi > n-k:
quickSort(nums, low, pi-1, k)
if pi < n-k:
quickSort(nums, pi+1, high, k)
return nums[len(nums)-k]
return quickSort(nums, 0, len(nums)-1, k)
【思考】
一首《明日歌》送给大家，也希望自己能珍惜当下！
明日复明日，明日何其多。
我生待明日，万事成蹉跎。
世人苦被明日累，春去秋来老将至。
朝看水东流，暮看日西坠。
百年明日能几何？请君听我明日歌。
明日复明日，明日何其多！
日日待明日，万事成蹉跎。
世人皆被明日累，明日无穷老将至。
晨昏滚滚水东流，今古悠悠日西坠。
百年明日能几何？请君听我明日歌。
Python力扣题解系列持续更新，欢迎
点赞收藏＋关注
上一篇：菜菜的刷题日记 | 118.杨辉三角
下一篇：菜菜的刷题日记 | 374.猜数字大小
本人水平有限，文章中不足之处欢迎下方👇评论区批评指正~如果感觉对你有帮助，点个赞👍 支持一下吧 ~
不定期分享 有趣、有料、有营养内容，欢迎 订阅关注 🤝 我的博客 ，期待在这与你相遇 ~
