赞
踩
目录
思路:利用快速排序思路,使用三指针分块进行优化。
- [0,left]——小于key
- [left+1,right-1]——等于key
- [right,nums.size()]——大于key
- class Solution {
- public:
- void sortColors(vector<int>& nums) {
- int n = nums.size();
- int left = -1, right = n, cur = 0;
- while (cur < right) {
- if (nums[cur] == 0)
- swap(nums[++left], nums[cur++]);
- else if (nums[cur] == 2)
- swap(nums[--right], nums[cur]);
- else
- cur++;
- }
- }
- };
思路:快排+三指针优化+随机选择基准元素
- class Solution {
- public:
- vector<int> sortArray(vector<int>& nums) {
- srand(time(NULL));
- qsort(nums,0,nums.size()-1);
- return nums;
- }
- int getRandom(vector<int>& nums,int left,int right){
- int i=rand();
- return nums[i%(right-left+1)+left];
- }
- void qsort(vector<int>& nums,int begin,int end){
- if(begin >= end)
- return;
- int i=begin,left=begin-1,right=end+1;
- int key=getRandom(nums,begin,end);
- while(i<right){
- if(nums[i]<key)
- swap(nums[++left],nums[i++]);
- else if(nums[i]>key)
- swap(nums[--right],nums[i]);
- else
- i++;
- }
- qsort(nums,begin,left);
- qsort(nums,right,end);
- }
- };
思路:快速选择(快排+三指针分块+随机选择基准元素+递归排序时进入对应区间)
- 第k个最大元素也就是排序(升序)后的倒数第k个
<key =key >key
|————|————————|—————|l left left+1 right-1 right r
a b c(区间元素个数)
c
表示在当前key(基准值)右侧的元素数量(即比key大的元素数量),b
表示等于key的元素数量。由于我们是寻找第k
个最大的元素,数组的右侧代表了较大的元素。
if (c >= k)
:如果key右侧的元素数量c
大于或等于k
,这意味着第k
个最大的元素位于key的右侧或者是key本身。因此,我们递归地在key右侧的数组部分继续进行快速选择,寻找第k
个最大的元素。
else if (b + c >= k)
:如果key右侧的元素数量c
加上等于key的元素数量b
大于或等于k
,这意味着第k
个最大的元素要么是key本身,要么在等于key的这些元素中。由于这些元素都是相等的,我们可以直接返回key
作为第k
个最大的元素。
else
:如果上述两个条件都不满足,这意味着第k
个最大的元素位于key的左侧。因此,我们递归地在pivot左侧的数组部分继续进行快速选择。此时,我们需要调整k
的值,因为我们已经排除了b + c
个比key大或等于key的元素,所以新的k
应该减去这部分已经排除的元素数量。
- class Solution {
- public:
- int findKthLargest(vector<int>& nums, int k) {
- srand(time(NULL));
- 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];
- int key = getRandom(nums, l, r);
- 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)
- swap(nums[--right], nums[i]);
- else
- i++;
- }
- 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 left, int right) {
- return nums[rand() % (right - left + 1) + left];
- }
- };
为了找到数组中第k个最大的元素,并且要求时间复杂度为O(n),我们可以比较这些方法:
快速选择算法(第一种方法):
最小堆(第二种方法):
- class Solution {
- public:
- int findKthLargest(vector<int>& nums, int k) {
- priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k);
- for(size_t i=k;i<nums.size();i++){
- if(nums[i]>pq.top()){
- pq.pop();
- pq.push(nums[i]);
- }
- }
- return pq.top();
- }
- };
排序(第三种方法):
- class Solution {
- public:
- int findKthLargest(vector<int>& nums, int k) {
- sort(nums.begin(),nums.end());
- return nums[nums.size()-k];
- }
- };
最大堆(第四种方法):
- class Solution {
- public:
- int findKthLargest(vector<int>& nums, int k) {
- priority_queue<int> pq(nums.begin(),nums.end());
- while(--k){
- pq.pop();
- }
- return pq.top();
- }
- };
结论:
综上所述,考虑到时间复杂度的要求和算法的效率,快速选择算法是最符合题目要求的解决方案
思路:快速选择(快排+三指针分块+随机选择基准元素+进入对应区间寻找)
<key =key >key
|————|————————|—————|l left left+1 right-1 right r
a b c(区间元素个数)
a
表示在当前的key(基准值)左边的元素数量,b
表示等于key的元素数量。cnt
是我们需要找到的库存余量最少的商品数量。
if (a > cnt)
:如果key左边的元素数量a
大于cnt
,这意味着我们需要的cnt
个最小元素全部位于key的左边。因此,我们递归地在key左边的数组部分继续进行快速选择,寻找这cnt
个最小元素。
else if (a + b >= cnt)
:如果key左边的元素数量a
加上等于key的元素数量b
大于或等于cnt
,这意味着我们需要的cnt
个最小元素已经包含在左边的元素和等于key的元素中。由于题目说明返回顺序不限,我们不需要进一步排序或选择,可以直接返回结果。
else
:如果上述两个条件都不满足,这意味着我们需要的cnt
个最小元素部分位于key的右边。因此,我们递归地在key右边的数组部分继续进行快速选择。此时,我们需要调整cnt
的值,因为我们已经找到了一部分所需的最小元素(即a + b
个),所以新的cnt
应该减去这部分已经找到的元素数量。
- class Solution {
- public:
- vector<int> inventoryManagement(vector<int>& stock, int cnt) {
- srand(time(NULL));
- qsort(stock, 0, stock.size() - 1, cnt);
- return {stock.begin(), stock.begin() + cnt};
- }
- int qsort(vector<int>& stock, int l, int r, int cnt) {
- if (l == r)
- return stock[l];
- int key = getRandom(stock, l, r);
- int left = l - 1, right = r + 1, i = l;
- while (i < right) {
- if (stock[i] < key)
- swap(stock[++left], stock[i++]);
- else if (stock[i] > key)
- swap(stock[--right], stock[i]);
- else
- i++;
- }
- int a = left - l + 1, b = right - left - 1;
- if (a > cnt)
- return qsort(stock, l, left, cnt);
- else if (a + b >= cnt)
- return 0;
- else
- return qsort(stock, right, r, cnt - b - a);
- }
- int getRandom(vector<int>& stock, int left, int right) {
- return stock[rand() % (right - left + 1) + left];
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。