LeetCode215给定整数数组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输出:4Python解法1.直接排序方法sortclass Solution: def findKthLargest(self, nums: List[int], k: int) - int: nums.sort() nums.reverse() count 0 for i in range(len(nums)): count 1 if count k : break return nums[count - 1]2.快速排序class Solution: def findKthLargest(self, nums: List[int], k: int) - int: def quickSelect(nums, kth): base random.choice(nums) small, equal, big [], [], [] for num in nums: if num base: big.append(num) elif num base: small.append(num) else: equal.append(num) if len(big) kth: return quickSelect(big, kth) if kth len(big) len(equal): new_k kth - (len(big) len(equal)) return quickSelect(small, new_k) return base return quickSelect(nums, k)Java解法仅展示快排class Solution { Random rand new Random(); public int findKthLargest(int[] nums, int k) { ArrayListInteger list new ArrayList(); for(int x : nums) list.add(x); return quickSelect(list, k); } private int quickSelect(ArrayListInteger arr, int kth) { if(arr.size() 1) return arr.get(0); // 对应 base random.choice(arr) int base arr.get(rand.nextInt(arr.size())); ArrayListInteger small new ArrayList(); ArrayListInteger equal new ArrayList(); ArrayListInteger big new ArrayList(); for(int num : arr) { if(num base) big.add(num); else if(num base) small.add(num); else equal.add(num); } if(big.size() kth) { return quickSelect(big, kth); } else if(big.size() equal.size() kth) { return base; } else { int newK kth - big.size() - equal.size(); return quickSelect(small, newK); } } }C解法#include vector #include random using namespace std; class Solution { public: int findKthLargest(vectorint nums, int k) { return quickSelect(nums, k); } private: int quickSelect(vectorint arr, int kth) { // 递归终止只剩一个元素直接返回 if (arr.size() 1) return arr[0]; // 等价 Python base random.choice(arr) random_device rd; mt19937 gen(rd()); uniform_int_distribution dist(0, arr.size() - 1); int idx dist(gen); int base arr[idx]; vectorint small, equal, big; for (int num : arr) { if (num base) big.push_back(num); else if (num base) small.push_back(num); else equal.push_back(num); } if (big.size() kth) { return quickSelect(big, kth); } else if (big.size() equal.size() kth) { return base; } else { int newK kth - big.size() - equal.size(); return quickSelect(small, newK); } } };快速排序解析一、核心思想分治 挖坑 / 双指针交换选基准 pivot从数组挑一个数作为分界值分区 partition把小于 pivot 放左边大于 pivot 放右边pivot 落到最终正确位置递归对 pivot 左、右两个子数组重复上述步骤直到子数组长度≤1天然有序二、算法特性平均时间复杂度\(O(n\log n)\)最坏时间复杂度\(O(n^2)\)数组已有序选首 / 尾当基准空间复杂度\(O(\log n)\) 递归栈最坏\(O(n)\)不稳定排序相等元素相对顺序会打乱原地排序不需要额外数组