题目

给定整数数组 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 <= 10^5
• -10^4 <= nums[i] <= 10^4

解答

源代码

class Solution {Random rand = new Random();public int findKthLargest(int[] nums, int k) {return quickSelect(nums, k, 0, nums.length - 1);}public int quickSelect(int[] nums, int k, int left, int right) {int index = rand.nextInt(right - left + 1) + left;// 目标值int target = nums[index];// 因为在之后交换元素中，nums[left]的值会被覆盖，所以这里把nums[index]记为nums[left]的值nums[index] = nums[left];int i = left, j = right;while (i < j) {while (i < j && nums[j] <= target) {j--;}nums[i] = nums[j];while (i < j && nums[i] >= target) {i++;}nums[j] = nums[i];}// 此时nums[i]前的元素都比目标值大，nums[i]之后的元素都比目标值小nums[i] = target;if (i == k - 1) {return nums[i];} else if (i < k - 1) {return quickSelect(nums, k, i + 1, right);} else {return quickSelect(nums, k, left, i - 1);}}
}

总结

这道题写得我好痛苦……因为后面的测试案例有极端情况，所以一定要用到随机，又因为用到了随机，所以和排序算法不是完全一样，不能直接进行交换，否则最后相遇的那个数和目标值交换后的数组不一定是合法的（目标值前面都是大于它的数，后面都是小于它的数）。