给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
思路:最开始排序算法,弄完之后直接按照要求选择,可惜题目对时间复杂度有要求,只能上快排,但是快排并不是直接满足,还需要在基础上优化。快排采取分治的思想,正常递归需要子串都进行排序,最后合并,但是找出结果有个便利的点就是可以判断在那个串里面,选择性的进行快排来加速。
#include <iostream>
#include <vector>
using namespace std;
//选择排序
// class Solution {
// public:
// int findKthLargest(vector<int>& nums, int k) {
// for (int i = 0; i < nums.size(); i++){
// int min_index = i; // 记录最小值的索引
// for (int j = i; j < nums.size(); j++){
// if (nums[j] < nums[min_index]){
// min_index = j;
// }
// }
// swap(nums[min_index], nums[i]);
// }
// return nums[nums.size() - k];
// }
// };
class Solution {
public:
int aparthSort(vector<int>& nums, int left, int right){
int i = left, j = right;
int pivot = nums[left];
while (i < j) {
while (i < j) {
if (nums[j] < pivot) {
nums[i] = nums[j];
i++;
break;
}
else
j--;
}
while (i < j) {
if (nums[i] > pivot) {
nums[j] = nums[i];
j--;
break;
}
else
i++;
}
}
nums[i] = pivot;
return i;
}
int sort (vector<int>& nums, int left, int right, int k) {
int mid;
if (left < right){
mid = aparthSort(nums, left, right);
if (mid == nums.size() - k) return nums[mid];
else if (mid > nums.size() - k) return sort(nums, left, mid - 1, k);
else return sort(nums, mid + 1, right, k);
}
else return nums[nums.size() - k];
}
int findKthLargest(vector<int>& nums, int k) {
int res = sort(nums, 0, nums.size() - 1, k);
return res;
}
};
int main(){
Solution s;
vector<int> nums = {3,2,1,5,6,4};
// vector<int> nums = {1};
int k = 4;
cout << s.findKthLargest(nums, k) << endl;
for (int i = 0; i < nums.size(); i++){
cout << nums[i] << " ";
}
return 0;
}