在未排序的数组中找到第 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 ≤ 数组的长度。
这道题是一道中等难度的题目，其实使用编程语言的内部的排序函数可以很简单的解决，
所以借此机会复习一下经典的两个排序算法，归并排序和快速排序，挑这两个的原因是因为他们都是利用D&C（分治）的思想。
⚠️ 注意题目中的排序是从大到小
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
#self._qsort(nums, 0, len(nums) - 1)
nums = self._msort(nums)
return nums[k - 1]
def _qsort(self, nums, start, end):
if start >= end:
return
pivot = start
left = pivot
right = end
while left < right:
while left < right and nums[right] < nums[pivot]:
right -= 1
while left < right and nums[left] >= nums[pivot]:
left += 1
nums[left], nums[right] = nums[right], nums[left]
nums[left], nums[pivot] = nums[pivot], nums[left]
self._qsort(nums, start, left - 1)
self._qsort(nums, left + 1, end)
def _msort(self, nums):
"""
归并排序
"""
length = len(nums)
if length < 2:
return nums
mid = length // 2
left = self._msort(nums[:mid])
right = self._msort(nums[mid:])
tmp = []
while left and right:
if left[0] > right[0]:
tmp.append(left.pop(0))
else:
tmp.append(right.pop(0))
if left:
tmp += left
else:
tmp += right
return tmp
《97 Things Every Programmer Should Know》- Beauty Is in Simplicity
在开发过程中，我们要努力让自己写的代码要有：
而代码是否优雅美观是一个很主观的感受，但是美观的代码肯定是简洁的。
Beauty of style and harmony and grace and good rhythm depends on simplicity.
推荐一个手机和平板的终端工具，https://termius.com/。
个人在日常生活中经常有一些代码的点子需要写下来运行一下，这时候就需要一个终端连接到我的 vps 上跑一下我的代码。
非常喜欢它的交互方式，感兴趣的可以体验一下。
