当前位置: 首页 > news >正文

哪个网站做ppt赚钱想建立自己的网站

哪个网站做ppt赚钱,想建立自己的网站,网络推广公司营销策划,代理公司注册代理本篇博客记录分治快排的4道题目&#xff1a;颜色分类、排序数组、数组中的第K个最大元素、数组中最小的N个元素&#xff08;库存管理&#xff09;。 class Solution { public:void sortColors(vector<int>& nums) {int n nums.size();int left -1,right n;for(int…

本篇博客记录分治快排的4道题目:颜色分类、排序数组、数组中的第K个最大元素、数组中最小的N个元素(库存管理)。

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int left = -1,right = n;for(int i = 0 ; i < right ; ){if(nums[i] == 0) swap(nums[++left],nums[i++]);else if(nums[i] == 1) i++;else swap(nums[--right],nums[i]);}}
};

题目分析:本题的目的旨在将nums的元素0、1、2分成三块,打算采取三指针的方法。使用left、right、i三个变量,其中,left指向全0区间的最右侧,right指向全2区间的最左侧,i指向待扫描的下一个元素,这样就把整个区间划分为4块,包括:

[0,left]:全0区域

[left+1,i-1]:全1区域

[i,right-1]:待扫描的区域

[right,n-1]:全2区域

划分好区域后,刚开始让left指向nums的左侧,即left=-1,right指向nums的右侧,即right=n,i指向nums中的第一个元素,nums[i]就会有三种情况:0、1、2。对于这三种情况,处理的动作如下图:

class Solution {
public:int GetRef(vector<int>& nums , int left , int right){return nums[rand()%(right - left + 1) + left];}void _sortArray(vector<int>& nums, int left, int right){if(left >= right) return;int ref = GetRef(nums, left, right);int l = left - 1, r = right + 1, i = left;while(i < r){if(nums[i] < ref) swap(nums[++l],nums[i++]);else if(nums[i] == ref) i++;else swap(nums[--r],nums[i]);}//[left,l] [l+1,r-1] [r,right] _sortArray(nums,left,l);_sortArray(nums,r,right);}vector<int> sortArray(vector<int>& nums) {srand(time(NULL));_sortArray(nums, 0 , nums.size() - 1);return nums;}
};

题目分析:我们实现快排要用到“颜色分类”这道题的思想,向数组划分为三块,

这样迭代一次之后,[left+1,right-1]之间的元素已经排好,继续递归[0,left]和[right,n-1]即可。

在选择基准元素key时,我们可以使用随机的方式选取,ref = nums[rand()%(right-left+1)+left]。

class Solution {
public:int GetRef(vector<int>& nums,int left, int right){return nums[rand()%(right-left+1)+left];}int sort(vector<int>& nums,int left, int right, int k){if(left == right) return nums[left];//1.随机选择基准元素int ref = GetRef(nums, left, right);//2.根据基准元素将数组分三块int l = left-1,r = right+1;for(int i = left ; i < r ; ){if(nums[i] < ref) swap(nums[i++],nums[++l]);else if(nums[i] > ref) swap(nums[i],nums[--r]);else i++;}//3.分情况讨论//[left,l][l+1,r-1][r,right]int c = right - r + 1, b = r - l -1;if(c >= k) return sort(nums,r,right,k);else if(b+c >= k) return ref;else return sort(nums,left,l,k-b-c);}int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return sort(nums,0,nums.size()-1,k);}
};

题目分析:这道题的基础依然是上面数组分三块+随机选择基准元素的思想,我们第一次将数组分成三块,[left,l][l+1,r-1][r,right],假设这三个区间的长度分别是a、b、c,然后分情况讨论:

1)c>=k,去[r,right],找第k大

2)b+c>=k,返回ref

3)如果1)和2)不成立,去[l,left],找第k-b-c大        

class Solution {
public:vector<int> inventoryManagement(vector<int>& nums, int cnt) {srand(time(nullptr));qsort(nums,0,nums.size()-1,cnt);return {nums.begin(),nums.begin()+cnt};}int GetRef(vector<int>& nums,int left,int right){return nums[rand()%(right-left+1)+left];}void qsort(vector<int>& nums,int left,int right,int cnt){if(left == right) return;int ref = GetRef(nums,left,right);int l = left - 1,r = right + 1,i = left;while(i < r){if(nums[i] < ref) swap(nums[++l],nums[i++]);else if(nums[i] > ref) swap(nums[--r],nums[i]);else i++;}//[left,l][l+1,r-1][r,right]int a = l - left + 1,b = r - 1 - (l + 1) + 1,c = right -r + 1;if(a > cnt) qsort(nums,left,l,cnt);else if(a + b >= cnt) return;else qsort(nums,r,right,cnt - a - b);}
};

题目分析:这道题我们有多种解法,解法1是把这些数放到一个容器中,然后进行排序,时间复杂度是OlogN。解法2是把这些数放到一个大堆里,取堆顶元素,时间复杂度是OlogK。我们这里用第三种解法,快速排序,也是利用数组分三块+随机选择基准元素的思想,在使用这个排序完一遍后,数组被分成了三块,[left,l][l+1,r-1][r,right],假设这几块的区间长度分别为a、b、c:

① a>k,继续在[left,l]中找出最小的元素。

② a+b>=k,直接返回

③ ①和②都不成立,找[right,r]中最小的k-a-b个元素,在加上[left,l]和[l+1,r-1]之间的元素。

http://www.dinnco.com/news/58833.html

相关文章:

  • 一个网站多久能做完网络营销毕业论文8000字
  • 拐角型网站aso关键词优化计划
  • 广州哪里有做网站的如何推广app
  • 网站收缩广告关键词优化网站排名
  • 搬瓦工可以做网站吗网站怎么被收录
  • 云南网站建设一度科技公司东莞网站营销策划
  • 专做韩国代购的网站免费发布广告的网站
  • 北京做微信网站制作企业网站的公司
  • 海口网站建设服务公司百度知道网页版登录入口
  • 新做的网站怎样推广企业seo
  • 电子商城网站源码谷歌搜索引擎363入口
  • asp网站伪静态规则“跨年”等关键词搜索达年内峰值
  • 余杭区建设规划局网站网络营销的成功案例有哪些
  • 做网站简单还是写程序seo排名推广工具
  • WordPress个人主页404网络优化工具app手机版
  • 网站设计自己申请南昌百度搜索排名优化
  • b2b电子商务平台都有哪些网站seo培训
  • 管理网站怎么做一键建站
  • 手机网站切图html网页模板
  • 工作号做文案素材的网站天津关键词优化专家
  • access 可以做网站不seo整站优化外包公司
  • erp软件销售seo关键词排名优化是什么
  • 怎样在b2b网站做推广有效果seo推广是什么意思呢
  • 辽宁省网站制作如何投放网络广告
  • 建设一个征婚网站的程序青岛官网优化
  • 专业网站建设好不好产品宣传方式有哪些
  • 天津网站优化公司爱站网长尾挖掘工具
  • asp网站开发技术背景介绍seo搜索引擎优化哪家好
  • 美发店网站源码营销推广的特点是
  • 做网站的那些事整站优化系统