我要评论题目：数组中的第K个最大元素
在未排序的数组中找到第 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 ≤ 数组的长度。
思路：
方法1：最简单的方法就是调用排序的库函数，对数组的元素先进行排序，然后找出第K个最大值（当然这个方法很简单，无法显示编程的水平）
方法2：对于方法1来说，几乎所有编程语言提供的排序的库函数都是基于快速排序而设计的，然而快排的具体实现是如何的呢，接下来，我将手撸快排代码来解决这个问题。
方法3：堆排序方法，建立一个大根堆，删除根节点（并不是完全删除，而是替换到最后面），然后自我调节，第二大的元素就会被交换上来，成为最大的新堆顶，重复上述操作，直到我们所要的第K个最大值成为堆顶节点，然后进行输出根节点的值。
快排原理
1.在数据集中，选择一个元素作为pivot（基准）
2.所有小于“基准”的元素，都移到“基准”的左边；所有大于“基准”的元素，都移到“基准”的右边。这个操作称为partition（分区）
3.对“基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有的子集只剩下一个元素为止。
选择基准pivot
1.选择第一个元素作为基准
2.随机选择一个元素作为基准
快排的平均时间复杂度是，最坏情况下的时间复杂度是，且是一种不稳定的排序方法。
python代码（快排实现）：
class Solution:
def findKthLargest(self, nums, k):
# 快排
self._k = len(nums) - k
return self.quicksort(nums, 0, len(nums) - 1)
def quicksort(self, nums, left, right):
if left == right:
return nums[left]
pivot = self.partition(nums, left, right)
if pivot == self._k:
return nums[pivot]
elif pivot < self._k:
return self.quicksort(nums, pivot + 1, right)
else:
return self.quicksort(nums, left, pivot - 1)
def partition(self, nums, left, right):
pivot = nums[left]
i, j = left, right
while i < j:
while i < j and nums[j] >= pivot:
j -= 1
if i < j:
nums[i] = nums[j]
i += 1
while i < j and nums[i] <= pivot:
i += 1
if i < j:
nums[j] = nums[i]
j -= 1
nums[i] = pivot
return i
堆排序
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。
复杂度：假设二叉堆总共有n个元素，那么向下调整的最坏时间复杂度就等同于二叉堆的高度，也就是
python代码（堆排序实现）
class Solution:
def findKthLargest(self, nums, k):
# 堆排
self._k = len(nums) - k
return self.heapsort(nums)
def heapsort(self, nums):
self.build_heap(nums)
for i in range(len(nums) - 1, self._k - 1, -1):
nums[i], nums[0] = nums[0], nums[i]
# 这里要排除最后一个元素
self.max_heapify(nums, 0, i)
return nums[self._k]
def build_heap(self, nums):
length = len(nums)
for i in range(((length - 1) // 2), -1, -1):
# 从最后一个节点的父节点开始向上调整
self.max_heapify(nums, i, length)
def max_heapify(self, nums, i, length):
left = i * 2 + 1
right = i * 2 + 2
if left < length and nums[left] > nums[i]:
largest = left
else:
largest = i
if right < length and nums[right] > nums[largest]:
largest = right
if largest != i:
nums[i], nums[largest] = nums[largest], nums[i]
# 子树也要调整
self.max_heapify(nums, largest, length)
快排与堆排的时间对比
从结果上看堆排序的运行时间比快排的速度快了10倍，理论上来说，两者的时间复杂度应该差不多，但是为什么出现这样的结果呢，原因应该是黑盒中的测试集数据的设置对堆排序更加友好。
提交提示：
和其他OJ完全不一样，LeetCode的代码不需要你print，甚至不需要你有主函数。它唯一有的就是一个叫做Solution的类，类中有一个函数，返回值和参数都给你写好了，算是一个提示吧。
在这种情况下我们提交代码就要注意以下几点：
1.完全不用担心头文件的问题，他都给你补全好了。
2.你不需要自己补全主函数，只要能够写出可以跑的目标函数就可以了。
3.如果需要引入其他函数，可以直接写在类里面。
本文地址：https://blog.csdn.net/ZXM_SHU/article/details/107105486
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论