代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给定整数数组 nums
和整数 k
,请返回数组中第 k
个最大的元素。
请注意,你需要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。
示例 1:
[3,2,1,5,6,4] 和
示例 2:
[3,2,3,1,2,4,5,5,6] 和
提示:
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
注意:本题与主站 215 题相同: https://leetcode.cn/problems/kth-largest-element-in-an-array/
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def quick_sort(left, right, k):
if left == right:
return nums[left]
i, j = left - 1, right + 1
x = nums[(left + right) >> 1]
while i < j:
while 1:
i += 1
if nums[i] >= x:
break
while 1:
j -= 1
if nums[j] <= x:
break
if i < j:
nums[i], nums[j] = nums[j], nums[i]
if j < k:
return quick_sort(j + 1, right, k)
return quick_sort(left, j, k)
n = len(nums)
return quick_sort(0, n - 1, n - k)
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
return quickSort(nums, 0, n - 1, n - k);
}
private int quickSort(int[] nums, int left, int right, int k) {
if (left == right) {
return nums[left];
}
int i = left - 1, j = right + 1;
int x = nums[(left + right) >>> 1];
while (i < j) {
while (nums[++i] < x)
;
while (nums[--j] > x)
;
if (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
if (j < k) {
return quickSort(nums, j + 1, right, k);
}
return quickSort(nums, left, j, k);
}
}
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
return quickSort(nums, 0, n - 1, n - k);
}
int quickSort(vector<int>& nums, int left, int right, int k) {
if (left == right) return nums[left];
int i = left - 1, j = right + 1;
int x = nums[left + right >> 1];
while (i < j) {
while (nums[++i] < x)
;
while (nums[--j] > x)
;
if (i < j) swap(nums[i], nums[j]);
}
return j < k ? quickSort(nums, j + 1, right, k) : quickSort(nums, left, j, k);
}
};
func findKthLargest(nums []int, k int) int {
n := len(nums)
return quickSort(nums, 0, n-1, n-k)
}
func quickSort(nums []int, left, right, k int) int {
if left == right {
return nums[left]
}
i, j := left-1, right+1
x := nums[(left+right)>>1]
for i < j {
for {
i++
if nums[i] >= x {
break
}
}
for {
j--
if nums[j] <= x {
break
}
}
if i < j {
nums[i], nums[j] = nums[j], nums[i]
}
}
if j < k {
return quickSort(nums, j+1, right, k)
}
return quickSort(nums, left, j, k)
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。