题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 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 <= 104-104 <= nums[i] <= 104
注意：本题与主站 215 题相同： https://leetcode.cn/problems/kth-largest-element-in-an-array/
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | 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);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | 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);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | 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)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | class Solution {
func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
var nums = nums
let n = nums.count
return quickSelect(&nums, 0, n - 1, n - k)
}
private func quickSelect(_ nums: inout [Int], _ left: Int, _ right: Int, _ k: Int) -> Int {
if left == right {
return nums[left]
}
var i = left - 1
var j = right + 1
let pivot = nums[(left + right) / 2]
while i < j {
repeat { i += 1 } while nums[i] < pivot
repeat { j -= 1 } while nums[j] > pivot
if i < j {
nums.swapAt(i, j)
}
}
if j < k {
return quickSelect(&nums, j + 1, right, k)
}
return quickSelect(&nums, left, j, k)
}
}
|