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。