合肥做淘宝网站,北京做网站费用,校园网站建设的优点,其它类型的定制营销型网站给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 思路#xff1a;最开始排序算法请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 思路最开始排序算法弄完之后直接按照要求选择可惜题目对时间复杂度有要求只能上快排但是快排并不是直接满足还需要在基础上优化。快排采取分治的思想正常递归需要子串都进行排序最后合并但是找出结果有个便利的点就是可以判断在那个串里面选择性的进行快排来加速。 #include iostream
#include vectorusing namespace std;
//选择排序
// class Solution {
// public:
// int findKthLargest(vectorint 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(vectorint 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;}elsei;}}nums[i] pivot;return i;}int sort (vectorint 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(vectorint nums, int k) {int res sort(nums, 0, nums.size() - 1, k);return res;}
};int main(){Solution s;vectorint nums {3,2,1,5,6,4};// vectorint nums {1};int k 4;cout s.findKthLargest(nums, k) endl;for (int i 0; i nums.size(); i){cout nums[i] ;}return 0;
}
