3 月 9 日 每日一题
题目：215. Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
1
2
| eg: Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
|
思路
这道题使用了 quickSort 的写法，通过 getPartition 找到第 n/2 大的位置，然后进行 while 循环直到找到 kth largest return。
尝试了另一种 Partition 的写法，个人感觉还是 swap 写法更易于理解。
本题应该还有其他解法，之后可能会做扩展。
因为明天 370 考试，故请假一天。
代码
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
| class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int left = 0;
int right = nums.size() - 1;
int target = nums.size() - k;
while(left < right){
int mid = findPartition(nums, left, right);
if(mid == target)
return nums[mid];
else if(mid < target)
left = mid + 1;
else
right = mid - 1;
}
return nums[left];
}
int findPartition(vector<int>& nums, int left, int right){
int pivot = nums[left];
while(left < right){
while(left < right && nums[right] >= pivot)
right--;
nums[left] = nums[right];
while(left < right && nums[left] <= pivot)
left++;
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}
};
|