LeetCode-215：数组中的第K个最大元素（快排与堆排）

题目：数组中的第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.随机选择一个元素作为基准

快排的平均时间复杂度是$O(nlogn)$，最坏情况下的时间复杂度是$O(n^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个元素，那么向下调整的最坏时间复杂度就等同于二叉堆的高度，也就是$O(nlogn)$

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.如果需要引入其他函数，可以直接写在类里面。