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

1. 题目描述

题目中转：215. 数组中的第K个最大元素

2.详细题解

    快速排序算法在每一轮排序中，随机选择一个数字$x$，根据与$x$的大小关系将要排序的数据分成独立的两个部分，其中一部分的所有数据都比$x$小（不比$x$大），另外一部分的所有数据比$x$要大（不比$x$小），此时一定可以确定$x$的位置为$mid$，若该位置$mid$即为要查找的第$k$元素，则已经找到答案，而不用关心左右两个区间中的数字是否有序。
  具体的，在实现过程中，若该位置$mid$大于$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);}
}

  执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一般是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络环境、当前提交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code。