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

个人做跨境电商网站找资源

个人做跨境电商网站,找资源,博客社区类网站模板下载,python 网站开发实战快乐的流畅:个人主页 个人专栏:《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火,在为久候之人燃烧! 文章目录 引言一、颜色分类二、排序数组三、数组中的第k个数四、最小的k个数总结 引言 本节主要介绍快速排序&#xf…



快乐的流畅:个人主页


个人专栏:《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火,在为久候之人燃烧!

文章目录

  • 引言
  • 一、颜色分类
  • 二、排序数组
  • 三、数组中的第k个数
  • 四、最小的k个数
  • 总结

引言

本节主要介绍快速排序(三路划分,随机取key),以及它的变形算法——快速选择算法

一、颜色分类


细节:快速排序中标准的partition(三路划分)

  • 设置三个指针 left,cur,right
  • 划分为三个区域[0, left - 1],[left, right],[right + 1, n-1]
  • [0, left - 1]:元素小于key
  • [left, right]:元素等于key
  • [right + 1, n-1]:元素大于key
  • left和right用来维护(等于key的)中路元素区域的左右两端,cur用来扫描数组
class Solution
{
public:void sortColors(vector<int>& nums){int left = 0, cur = 0, right = nums.size() - 1;while(cur <= right){if(nums[cur] == 0) swap(nums[left++], nums[cur++]);else if(nums[cur] == 2) swap(nums[right--], nums[cur]);else ++cur;}}
};

二、排序数组


思路:

  • 递归出口:区间只有一个元素或者不存在
  • 随机选key:利用rand函数,记得提前srand种下随机数种子
  • 三路划分:三指针维护区间
  • 分治:继续递归[begin, left - 1],[right + 1, end]两个区间
class Solution
{
public:int getKey(vector<int>& nums, int left, int right){int keyi = rand() % (right - left + 1) + left;return nums[keyi];}void quickSort(vector<int>& nums, int begin, int end){if(begin >= end) return;int key = getKey(nums, begin, end);//随机选keyint cur = begin, left = begin, right = end;while(cur <= right){if(nums[cur] < key) swap(nums[left++], nums[cur++]);else if(nums[cur] > key) swap(nums[right--], nums[cur]);else cur++;}quickSort(nums, begin, left - 1);quickSort(nums, right + 1, end);}vector<int> sortArray(vector<int>& nums){srand(0);//种下随机数种子quickSort(nums, 0, nums.size() - 1);return nums;}
};

三、数组中的第k个数


思路:TopK问题有三种解法

  1. 排序——O(NlogN)
  2. 堆——O(NlogK)
  3. 快速选择——O(N)

堆版本

细节:建大堆 + k-1次删除

class Solution
{
public:void AdjustDown(vector<int>& nums, int parent){int n = nums.size(), child = 2 * parent + 1;while(child < n){if(child + 1 < n && nums[child] < nums[child + 1]) ++child;if(nums[parent] < nums[child])//建大堆{swap(nums[parent], nums[child]);parent = child;child = 2 * parent + 1;}else break;}}int findKthLargest(vector<int>& nums, int k){int n = nums.size();for(int i=(n-1-1)/2; i>=0; --i){AdjustDown(nums, i);}while(--k)//执行k-1次{swap(nums[0], nums[nums.size() - 1]);nums.pop_back();AdjustDown(nums, 0);}return nums[0];}
};

快速选择版本

细节:

  • 从最右边开始数,k落在右区域,则继续递归找第k大
  • k落在中区域,则直接更新结果
  • k落在左区域,则继续递归找第k-b-c大
class Solution
{int ret;
public:int GetKey(vector<int>& nums, int begin, int end){int keyi = rand() % (end - begin + 1) + begin;return nums[keyi];}void qucikSelect(vector<int>& nums, int begin, int end, int k){if(begin > end) return;int key = GetKey(nums, begin, end);int left = begin, cur = begin, right = end;while(cur <= right){if(nums[cur] < key) swap(nums[left++], nums[cur++]);else if(nums[cur] > key) swap(nums[right--], nums[cur]);else cur++;}if(k <= end - right) qucikSelect(nums, right + 1, end, k);else if(k <= end - left + 1) ret = key;else qucikSelect(nums, begin, left - 1, k - (end - left + 1));}int findKthLargest(vector<int>& nums, int k){srand(0);qucikSelect(nums, 0, nums.size() - 1, k);return ret;}
};

四、最小的k个数



细节:

  • 从最左边开始数,k落在左区域,则继续递归找最小的k个元素
  • k落在中区域,则直接返回前k个元素
  • k落在右区域,则继续递归找最小的k-a-b个元素
class Solution
{
public:int getKey(vector<int>& nums, int begin, int end){int keyi = rand() % (end - begin + 1) + begin;return nums[keyi];}void quickSelect(vector<int>& nums, int begin, int end, int k){if(begin >= end) return;int key = getKey(nums, begin, end);int left = begin, cur = begin, right = end;while(cur <= right){if(nums[cur] < key) swap(nums[left++], nums[cur++]);else if(nums[cur] > key) swap(nums[right--], nums[cur]);else cur++;}if(k <= left - begin) quickSelect(nums, begin, left - 1, k);else if(k <= right + 1 - begin) return;else quickSelect(nums, right + 1, end, k - (right + 1 - begin));}vector<int> inventoryManagement(vector<int>& nums, int k){srand(0);quickSelect(nums, 0, nums.size() - 1, k);return {nums.begin(), nums.begin() + k};}
};

总结

快速排序,随机选key,保证了时间复杂度逼近O(NlogN),三路划分,是为了处理重复大量元素。

快速选择,是基于快速排序的变形算法,在解决TopK问题有着O(N)的时间复杂度,极其高效!


真诚点赞,手有余香

http://www.rdtb.cn/news/1476.html

相关文章:

  • 网站建设商虎小程序买淘宝店铺多少钱一个
  • 台州企业网站一元手游平台app
  • 晋江住房和城乡建设局网站临沂seo代理商
  • 网站建设技术合作合同书如何接广告赚钱
  • 可信网站认证必须做吧网站搜索引擎优化
  • 网站开发合作意向书精准营销包括哪几个方面
  • 旅游宣传推广方案在哪里可以免费自学seo课程
  • 上海仿站定制模板建站市场调研报告500字
  • 做网站客服的工作流程接广告的平台
  • 自己做网站要买什么醴陵网站制作
  • 万户网站建设公司学电脑培训班多少一个月
  • 网站建设企业最新报价深圳全网推广效果如何
  • 网站修改title北京seo专员
  • ks刷粉网站推广马上刷外贸网站推广公司
  • 网站内容为王昆明百度推广优化
  • 营销型网站建设公司推荐优化大师电脑版官方免费下载
  • 做b2b网站销售怎样让客户找上门石家庄新闻头条新闻最新今天
  • 做视频聊天网站找片子有什么好的关键词
  • 网站做拓扑图编辑软件编程培训学校排名
  • wordpress怎么上传自己的网站搜索引擎优化报告
  • 布吉附近做网站网站搜索优化技巧
  • 昆明网站排名优化价格网络推广方案设计
  • 国内做的比较大的外贸电商网站昭通网站seo
  • 承德市外贸网站建设seo点击排名源码
  • 网页设计教程实例项目网站的seo
  • 新闻网页制作模板seo综合查询平台官网
  • mac做网站改html文件知名的网络推广
  • 自己做的网站加载慢的原因公司网站推广费用
  • 学习网站建设的书沧州百度推广公司
  • 网站开发怎么自学seo排名关键词搜索结果