赞
踩
题目链接:数组中的第K个最大元素
这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。
在快速排序算法中,一种常见的优化策略是将数组划分为三个区间。这种划分方式可以更加精确地定位到目标元素所在的位置,从而加快排序速度。具体地,这三个区间为:[l, left]、[left + 1, right - 1] 和 [right, r]。
- class Solution
- {
- public:
- int findKthLargest(vector<int>& nums, int k)
- {
- srand(time(nullptr));
- return qsort(nums, 0, nums.size() - 1, k);
- }
- int qsort(vector<int>& nums, int l, int r, int k)
- {
- if(l == r) return nums[l];
-
- //1.随机算则一个基准元素
- int key = getRandom(nums, l, r);
- //2.将数组分三块
- int left = l - 1, right = r + 1, i = l;
- while(i < right)
- {
- if(nums[i] < key) swap(nums[++left], nums[i++]);
- else if(nums[i] == key) i++;
- else swap(nums[--right], nums[i]);
- }
- //3.分情况讨论
- int c = r - right + 1, b = right - left - 1;
- if(c >= k)
- {
- return qsort(nums, right, r, k);
- }
- else if(b + c >= k)
- {
- return key;
- }
- else
- {
- return qsort(nums, l, left, k -b -c);
- }
- }
- int getRandom(vector<int>& nums, int l, int r)
- {
- return nums[rand() % (r - l + 1) + l];
- }
- };
嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。
觉得有点收获的话,不妨给我点个赞吧!
如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。