JAVA练习347- 数组中的第K个最大元素

题目概览给定整数数组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来源215. 数组中的第K个最大元素 - 力扣LeetCode解题分析方法快速排序根据快排的思路每个都是选取第一个值作为标识将小于它的元素放在左边大于它的元素放在右边令当前索引为 mid那么该元素就是第 n - mid 大的元素。令左边界为 start右边界为 end当 k mid 时往 [mid, end] 继续重复操作当 k mid 时往 [ start, end - 1] 继续重复操作直到找到第 k 大的元素。时间复杂度O(n)空间复杂度O(logn)class Solution { public int findKthLargest(int[] nums, int k) { int n nums.length; return quickSelect(nums,n - k, 0, n - 1); } public int quickSelect(int[] nums, int k, int start, int end) { if (start end) { return nums[k]; } int x nums[start]; int i start - 1, j end 1; while(i j) { do i; while (nums[i] x); do j--; while (nums[j] x); if (i j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } } if (k j) { return quickSelect(nums, k, start, j); } return quickSelect(nums, k, j 1, end); } }