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

艺术公司网站定制中心做网站排名优化的公司

艺术公司网站定制中心,做网站排名优化的公司,邢台县建设局网站,佛山网站架设目录 1--归并排序 2--小和问题 3--逆序对问题 1--归并排序 归并排序的核心思想&#xff1a;将一个无序的序列归并排序为一个有序的系列&#xff1b;通过递归将无序的序列二分&#xff0c;从底层开始将二分的序列归并排序为有序序列&#xff1b; #include <iostream> #…

目录

1--归并排序

2--小和问题

3--逆序对问题


1--归并排序

        归并排序的核心思想:将一个无序的序列归并排序为一个有序的系列;通过递归将无序的序列二分,从底层开始将二分的序列归并排序为有序序列;

#include <iostream>
#include <vector>class Solution{
public:std::vector<int> Merge_Sort(std::vector<int> arr){if(arr.size() <= 1) return arr;split(arr, 0, arr.size() - 1);return arr;}// 二分void split(std::vector<int> &arr, int l, int r){if(l == r) return;int mid = l + (r - l) / 2;split(arr, l, mid);split(arr, mid+1, r);// 归并merge(arr, l, mid, mid+1, r);}void merge(std::vector<int> &arr, int l1, int r1, int l2, int r2){std::vector<int> res;int i = l1, j = l2;while(i <= r1 && j <= r2){if (arr[i] < arr[j]){res.push_back(arr[i]);i++;}else{res.push_back(arr[j]);j++;}}while(i <= r1){res.push_back(arr[i]);i++;}while(j <= r2){res.push_back(arr[j]);j++;}for(int i = 0, j = l1; j <= r2; i++, j++){arr[j] = res[i];}}
};int main(){std::vector<int> input = {1, 3, 4, 2, 5};Solution S1;std::vector<int> res = S1.Merge_Sort(input);for(int num : res) std::cout << num << " ";return 0;
}

2--小和问题

        在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和,请编码实现求解一个数组的小和;

        实例,给定数组 [1, 3, 4, 2, 5],1 左边比 1 小的数,没有;3 左边比 3 小的数, 为 1;4 左边比 4 小的数, 为 1 和 3;2 左边比 2 小的数,为 1;5 左边比 5 小的数,为 1, 3, 4 和 2;因此数组的小数和为:1 + (1+3) + (1) + (1+3+4+2) = 16;

主要思路:

        在归并排序两两比较两个数组的元素时,就确定对应的小数和;具体做法是,分析当前数是另一个数组中多少个数的小数,即当前数多少次被用于计算小数和;

#include <iostream>
#include <vector>class Solution{
public:int Merge_Sort(std::vector<int> arr){if(arr.size() <= 1) return 0;int sum = split(arr, 0, arr.size() - 1);return sum;}// 二分int split(std::vector<int> &arr, int l, int r){if(l == r) return 0;int mid = l + (r - l) / 2;int count1 = split(arr, l, mid);int count2 = split(arr, mid+1, r);int count3 = merge(arr, l, mid, mid+1, r);// 归并return count1 + count2 + count3;}int merge(std::vector<int> &arr, int l1, int r1, int l2, int r2){int sum = 0;std::vector<int> res;int i = l1, j = l2;while(i <= r1 && j <= r2){if (arr[i] < arr[j]){// 对于 arr[j, r2] 的数都会大于 arr[i],因此它们的小数和都包含arr[i]sum += (r2 - j + 1) * arr[i];res.push_back(arr[i]);i++;}else{res.push_back(arr[j]);j++;}}while(i <= r1){res.push_back(arr[i]);i++;}while(j <= r2){res.push_back(arr[j]);j++;}for(int i = 0, j = l1; j <= r2; i++, j++){arr[j] = res[i];}return sum;}
};int main(){std::vector<int> input = {1, 3, 4, 2, 5};Solution S1;int res = S1.Merge_Sort(input);std::cout << res << " " << std::endl;return 0;
}

3--逆序对问题

主要思路:

        在归并排序两两比较两个数组的元素时,就确定对应的逆序对;具体做法是,分析当前数(arr2)在另一个数组(arr1)中有多少个逆序数

#include <iostream>
#include <vector>class Solution{
public:int Merge_Sort(std::vector<int> arr){if(arr.size() <= 1) return 0;int sum = split(arr, 0, arr.size() - 1);return sum;}// 二分int split(std::vector<int> &arr, int l, int r){if(l == r) return 0;int mid = l + (r - l) / 2;int count1 = split(arr, l, mid);int count2 = split(arr, mid+1, r);int count3 = merge(arr, l, mid, mid+1, r);// 归并return count1 + count2 + count3;}int merge(std::vector<int> &arr, int l1, int r1, int l2, int r2){int sum = 0;std::vector<int> res;int i = l1, j = l2;while(i <= r1 && j <= r2){if (arr[i] > arr[j]){// 对于 arr[j, r2] 的数都会大于 arr[i],因此它们的小数和都包含arr[i]sum += (r1 - i + 1);res.push_back(arr[j]);j++;}else{res.push_back(arr[i]);i++;}}while(i <= r1){res.push_back(arr[i]);i++;}while(j <= r2){res.push_back(arr[j]);j++;}for(int i = 0, j = l1; j <= r2; i++, j++){arr[j] = res[i];}return sum;}
};int main(){std::vector<int> input = {7, 5, 6, 4};Solution S1;int res = S1.Merge_Sort(input);std::cout << res << " " << std::endl;return 0;
}

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

相关文章:

  • 在家做网站维护兼职合肥头条今日头条新闻最新消息
  • 一般网站维护要多久宁波seo优化
  • jsp网站购物车怎么做全网推广外包公司
  • 如何查看网站日志文件网站收录提交入口网址
  • 邯郸网站优化怎么用网站seo查询
  • Wordpress滚动公告怎么做seo优化顾问
  • 信息网络安全包括新网站seo外包
  • 台州做网站比较好的有哪些自媒体135网站
  • 四川华泰建设集团网站免费行情网站
  • 河北手机版建站系统价格seo网站推广平台
  • 贵州华瑞网站建设有限公司百度竞价推广登录
  • 网站建设会计科目最近热点新闻事件2023
  • 阿里巴巴黄页网站seo点击
  • 广西做网站的公司有哪些做引流推广的平台
  • 北京企业官网网站建设哪家好seo网站优化专员
  • 网站滚动条平台代运营是什么意思
  • 个人网站论坛展示百度seo排名点击软件
  • wordpress 调用全文某网站seo诊断分析
  • 公众号官网登录搜索引擎排名优化
  • 如何自己做优惠券网站沈阳沈河seo网站排名优化
  • 网赢天下深圳网站建设最权威的品牌排行榜网站
  • 专门做设计的网站快速百度
  • 漯河住房建设局网站互联网十大企业
  • 建设网站赚广告费是否可行seo客服
  • 网站建设方案书 模板手机网址大全123客户端下载
  • 鞍山企业做网站强化防疫指导
  • 如何取一个大气的名字的做网站咸阳seo公司
  • 百度惠生活推广怎么收费云南seo简单整站优化
  • 合肥的网站建设剂屏前端优化网站
  • 自己做网站好还是购买网站好网站运营seo实训总结