北碚免费建站哪家做得好,近期新闻热点事件摘抄,线上平台名称大全,邵阳做网站的有哪些目录
1、75. 颜色分类
2、912. 排序数组
3、 215. 数组中的第K个最大元素
4、LCR 159. 库存管理 III 1、75. 颜色分类 思路#xff1a;利用快速排序思路#xff0c;使用三指针分块进行优化。 [0,left]——小于key[left1,right-1]——等于key[right,nums.size()]——大于k…目录
1、75. 颜色分类
2、912. 排序数组
3、 215. 数组中的第K个最大元素
4、LCR 159. 库存管理 III 1、75. 颜色分类 思路利用快速排序思路使用三指针分块进行优化。 [0,left]——小于key[left1,right-1]——等于key[right,nums.size()]——大于key class Solution {
public:void sortColors(vectorint 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]);elsecur;}}
};
2、912. 排序数组 思路快排三指针优化随机选择基准元素 class Solution {
public:vectorint sortArray(vectorint nums) {srand(time(NULL));qsort(nums,0,nums.size()-1);return nums;}int getRandom(vectorint nums,int left,int right){int irand();return nums[i%(right-left1)left];}void qsort(vectorint nums,int begin,int end){if(begin end)return;int ibegin,leftbegin-1,rightend1;int keygetRandom(nums,begin,end);while(iright){if(nums[i]key)swap(nums[left],nums[i]);else if(nums[i]key)swap(nums[--right],nums[i]);elsei;}qsort(nums,begin,left);qsort(nums,right,end);}
};
3、 215. 数组中的第K个最大元素 思路快速选择快排三指针分块随机选择基准元素递归排序时进入对应区间 第k个最大元素也就是排序(升序)后的倒数第k个 key key key |————|————————|—————| l left left1 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(vectorint nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}int qsort(vectorint 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]);elsei;}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;elsereturn qsort(nums, l, left, k - b - c);}int getRandom(vectorint nums, int left, int right) {return nums[rand() % (right - left 1) left];}
}; 为了找到数组中第k个最大的元素并且要求时间复杂度为O(n)我们可以比较这些方法 快速选择算法第一种方法: 优点: 平均时间复杂度为O(n)符合题目要求。它通过随机选择一个枢轴来分割数组然后只在包含第k个最大元素的那部分数组上递归从而减少了不必要的计算。缺点: 最坏情况下的时间复杂度为O(n^2)但这种情况很少发生。算法的性能依赖于随机数的选择。 最小堆第二种方法: 优点: 对于找到第k个最大元素这种方法维护了一个大小为k的最小堆时间复杂度为O(n log k)适合k远小于n的情况。缺点: 当k接近n时性能不如快速选择算法。 class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint,vectorint,greaterint pq(nums.begin(),nums.begin()k);for(size_t ik;inums.size();i){if(nums[i]pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();}
}; 排序第三种方法: 优点: 实现简单直观易懂。缺点: 时间复杂度为O(n log n)不满足题目对O(n)时间复杂度的要求。 class Solution {
public:int findKthLargest(vectorint nums, int k) {sort(nums.begin(),nums.end());return nums[nums.size()-k];}
}; 最大堆第四种方法: 优点: 通过构建一个最大堆然后弹出k-1次可以直接得到第k个最大元素。这种方法简单且对于理解堆结构很有帮助。缺点: 时间复杂度为O(n k log n)当k较小相对高效但当k接近n时性能下降。 class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint pq(nums.begin(),nums.end());while(--k){pq.pop();}return pq.top();}
};
结论:
如果你追求平均情况下的最优时间复杂度并且可以接受在极少数情况下性能的不确定性快速选择算法是最佳选择。如果k值较小最小堆方法也是一个不错的选择因为它可以较快地找到第k个最大的元素。排序方法虽然简单但不满足题目对时间复杂度的要求。最大堆方法适用于k值较小的情况但当k值较大时性能不是最优的。
综上所述考虑到时间复杂度的要求和算法的效率快速选择算法是最符合题目要求的解决方案
4、LCR 159. 库存管理 III 思路快速选择快排三指针分块随机选择基准元素进入对应区间寻找 key key key |————|————————|—————| l left left1 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:vectorint inventoryManagement(vectorint stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() cnt};}int qsort(vectorint 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]);elsei;}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;elsereturn qsort(stock, right, r, cnt - b - a);}int getRandom(vectorint stock, int left, int right) {return stock[rand() % (right - left 1) left];}
};
