215. 数组中的第K个最大元素（中等）

215. 数组中的第K个最大元素

1. 题目描述
2.详细题解
3.代码实现
- 3.1 Python
- 3.2 Java

1. 题目描述

题目中转：215. 数组中的第K个最大元素
在这里插入图片描述

2.详细题解

快速排序算法在每一轮排序中，随机选择一个数字 $x$ ，根据与 $x$ 的大小关系将要排序的数据分成独立的两个部分，其中一部分的所有数据都比 $x$ 小（不比 $x$ 大），另外一部分的所有数据比 $x$ 要大（不比 $x$ 小），此时一定可以确定 $x$ 的位置为 $mi d$ ，若该位置 $mi d$ 即为要查找的第 $k$ 元素，则已经找到答案，而不用关心左右两个区间中的数字是否有序。
具体的，在实现过程中，若该位置 $mi d$ 大于 $k$ ，说明 $k$ 在左区间，则递归左区间，否则递归右区间。
该题代码开发工作量略大，主要是边界问题的处理具体。在Python方法一中忽略了子区间仅为两个元素的情况，故造成错误；Python方法二和Java方法一为同一种算法代码实现，提交均为超出时间限制，未通过测试案例均为同一个，根本原因在于数组中存在大量的相同元素时，划分数组时未等分，以致于递归迭代深度太深，例如对于数组 $[1, 1, 1, 1, 1, 1, 1, 1]$ ，根据；Python方法二和Java方法一，初始化 $l = 0, r = 7$ ，第一次划分结果为 $i = 7, j = 0$ ，以 $j = 0$ 划分，对于测试未通过的案例，达到10万级的数组长度，且几乎所有数字均为 $1$ ，即为一个极端案例。【该题leetcode的官方题解非常清晰，建议仔细阅读。】

3.代码实现

3.1 Python

Python方法一：

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:n = len(nums)return self.quickSelect(nums, 0, n-1, n-k)def quickSelect(self, nums, l, r, k):i, j = l+1, rwhile i < j:while i < r and nums[i] <= nums[l]:i += 1while j > l and nums[j] >= nums[l]:j -= 1if i>=j:breaknums[i], nums[j] = nums[j], nums[i]nums[l], nums[j] = nums[j], nums[l]if k == j:return nums[j]elif k < j:return self.quickSelect(nums, l, j-1, k)else:return self.quickSelect(nums, j+1, r, k)

在这里插入图片描述
Python方法二：

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:n = len(nums)return self.quickSelect(nums, 0, n-1, n-k)def quickSelect(self, nums, l, r, k):i, j = l+1, rwhile l < r:while i < r and nums[i] <= nums[l]:i += 1while j > l and nums[j] >= nums[l]:j -= 1if i>=j: breaknums[i], nums[j] = nums[j], nums[i]nums[l], nums[j] = nums[j], nums[l]if k == j:return nums[j]elif k < j:return self.quickSelect(nums, l, j-1, k)else:return self.quickSelect(nums, j+1, r, k)

在这里插入图片描述
Python方法三：

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:n = len(nums)return self.quickSelect(nums, 0, n-1, n-k)def quickSelect(self, nums, l, r, k):if l == r:return nums[k]i, j, key = l-1, r+1, nums[l]while i < j:i += 1while nums[i] < key:i += 1j -= 1while nums[j] > key:j -= 1if i < j: nums[i], nums[j] = nums[j], nums[i]if k <= j:return self.quickSelect(nums, l, j, k)else:return self.quickSelect(nums, j+1, r, k)

在这里插入图片描述

3.2 Java

Java方法一：

class Solution {public int findKthLargest(int[] nums, int k) {int n = nums.length;return quickSelect(nums, 0, n-1, n-k);}public int quickSelect(int[] nums, int l, int r, int k){int i = l+1, j = r;while (l < r){while (i < r && nums[i] <= nums[l]){i++;}while (j > l && nums[j] >= nums[l]){j--;}if (i>=j){break;}int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}int tmp = nums[l];nums[l] = nums[j];nums[j] = tmp;if (j==k){return nums[j];}else if (k < j){return quickSelect(nums, l, j-1, k);}else{return quickSelect(nums, j+1, r, k);}}
}

在这里插入图片描述
Java方法二：

class Solution {public int findKthLargest(int[] nums, int k) {int n = nums.length;return quickSelect(nums, 0, n - 1, n - k);}public int quickSelect(int[] nums, int l, int r, int k) {if (l == r) return nums[k];int key = nums[l], i = l - 1, j = r + 1;while (i < j) {do i++; while (nums[i] < key);do j--; while (nums[j] > key);if (i < j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}if (k <= j) return quickSelect(nums, l, j, k);else return quickSelect(nums, j + 1, r, k);}
}