难度: Medium
给定整数数组 nums 和整数 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
提示：
1 <= k <= nums.length <= 104-104 <= nums[i] <= 104注意：本题与主站 215 题相同： https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
运行时间: 35 ms
内存: 16.7 MB
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums = sorted(nums)
return nums[-k]
这个题解的方法是直接排序整个数组，然后返回第 k 个最大元素。由于第 k 个最大元素相当于是从数组末尾开始第 k 个元素，因此可以通过索引 -k 来直接访问。这种方法直观易懂，但可能不是最优的解决方案，尤其在 k 远小于数组长度 n 的情况下。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# 对数组进行排序
nums = sorted(nums)
# 返回第 k 个最大的元素，即从末尾开始的第 k 个元素
return nums[-k]
快速排序是一种分治算法，其平均时间复杂度为O(n log n)，但在最坏情况下，时间复杂度可以退化为O(n^2)。快速排序在数据分布较为均匀时表现最佳。相比之下，Timsort是一种混合排序算法，结合了归并排序和插入排序的优点，专门优化了在实际数据中常见的有序模式。Timsort的最坏情况时间复杂度也是O(n log n)，但它通常在包含多个已排序或部分排序的序列的数据集上表现更好。因此，在处理大数据集时，尤其是当数据局部有序时，Timsort可能比快速排序有更稳定和更优的性能表现。
当k等于1或nums的长度等于1时，题解中的排序方法虽然可行，但不一定是最优解。例如，当k等于1时，即寻找最大元素，可以通过一次遍历（O(n)时间复杂度）完成，而无需进行完整的排序（O(n log n)时间复杂度）。同样，当数组长度为1时，任何查找都很简单，因为只有一个元元素。在这些特殊情况下，考虑到性能和效率，使用简单的遍历或其他更适合的方法（如最小/最大堆）可能更为合适。
通过索引-k访问数组元素通常是安全的，前提是数组已经正确排序并且k值是有效的。这种方法可能会失效或产生错误的情况包括：1) k的值超出了数组的范围，例如k大于数组长度或k为零或负数，导致索引错误；2) 数组未被正确排序或在排序过程中数据被意外修改，导致返回的结果不正确。因此，确保数组正确排序并严格验证k的值是使用这种访问方法的关键。