难度: Medium
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104运行时间: 61 ms
内存: 27.1 MB
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def find(nums,k):
big,small,equal=[],[],[]
pivot=random.choice(nums)
for num in nums:
if num>pivot:
big.append(num)
elif num<pivot:
small.append(num)
else:
equal.append(num)
if len(big)>=k:
res=find(big,k)
elif len(nums)-len(small)>=k:
res=pivot
else:
res=find(small,k-len(big)-len(equal))
return res
res=find(nums,k)
return res
这个题解使用了快速选择（QuickSelect）算法来找到数组中第k大的元素。其基本思路是：通过随机选择一个基准元素 pivot，将数组划分为三个部分：大于 pivot 的元素、小于 pivot 的元素和等于 pivot 的元素。根据这三部分元素的数量，可以确定第 k 大的元素在哪个部分中，然后递归地在相应的部分继续查找，直到找到第 k 大的元素。
时间复杂度: O(n)
空间复杂度: O(log n)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def find(nums,k):
big,small,equal=[],[],[]
pivot=random.choice(nums) # 随机选择基准元素
for num in nums:
if num>pivot:
big.append(num) # 大于 pivot 的元素
elif num<pivot:
small.append(num) # 小于 pivot 的元素
else:
equal.append(num) # 等于 pivot 的元素
if len(big)>=k: # 第 k 大的元素在 big 部分中
res=find(big,k)
elif len(nums)-len(small)>=k: # 第 k 大的元素是 pivot
res=pivot
else: # 第 k 大的元素在 small 部分中
res=find(small,k-len(big)-len(equal))
return res
res=find(nums,k)
return res
在快速选择算法中，如果总是选择固定位置的元素作为基准，如始终选择第一个元素或最后一个元素，当输入数组已经有序或接近有序时，算法性能会退化到O(n^2)。通过随机选择基准元素，可以使算法对于不同的输入在平均情况下表现更加稳定，大大减少了遭遇最坏情况的概率，从而确保算法在大多数情况下都能维持较好的性能（平均时间复杂度为O(n)）。
快速选择算法通过每次递归减少搜索的数组的大小来保证递归深度。因为每次都是随机选择基准元素，平均情况下，数组会被分成大小大致相等的两部分。这样每次递归都会排除约一半的元素，递归深度因此在平均情况下达到O(log n)。
当len(big) >= k时，这意味着所有在big数组中的元素都比pivot大，并且数量足以包含第k大的元素。因此，第k大的元素肯定不在equal数组中，这使得搜索可以直接在big数组中继续进行，无需考虑equal数组，从而提高了算法的效率。
是的，题解中的条件表述有误。正确的判断应该是：当big数组的长度小于k且当加上equal数组的长度后，k仍然不超过big数组和equal数组长度之和时，说明第k大的元素在equal数组中，且等于pivot。因此，正确的条件应该是len(nums) - len(small) - len(equal) < k <= len(nums) - len(small)。