如何开发一个视频网站,网站建设 怎么跑业务,wordpress更改图片,学科基地网站建设目录
1--归并排序
2--小和问题
3--逆序对问题 1--归并排序 归并排序的核心思想#xff1a;将一个无序的序列归并排序为一个有序的系列#xff1b;通过递归将无序的序列二分#xff0c;从底层开始将二分的序列归并排序为有序序列#xff1b; #include iostream
#…目录
1--归并排序
2--小和问题
3--逆序对问题 1--归并排序 归并排序的核心思想将一个无序的序列归并排序为一个有序的系列通过递归将无序的序列二分从底层开始将二分的序列归并排序为有序序列 #include iostream
#include vectorclass Solution{
public:std::vectorint Merge_Sort(std::vectorint arr){if(arr.size() 1) return arr;split(arr, 0, arr.size() - 1);return arr;}// 二分void split(std::vectorint arr, int l, int r){if(l r) return;int mid l (r - l) / 2;split(arr, l, mid);split(arr, mid1, r);// 归并merge(arr, l, mid, mid1, r);}void merge(std::vectorint arr, int l1, int r1, int l2, int r2){std::vectorint 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::vectorint input {1, 3, 4, 2, 5};Solution S1;std::vectorint res S1.Merge_Sort(input);for(int num : res) std::cout num ;return 0;
}
2--小和问题 在一个数组中每一个数左边比当前数小的数累加起来叫做这个数组的小和请编码实现求解一个数组的小和 实例给定数组 [1, 3, 4, 2, 5]1 左边比 1 小的数没有3 左边比 3 小的数 为 14 左边比 4 小的数 为 1 和 32 左边比 2 小的数为 15 左边比 5 小的数为 1, 3, 4 和 2因此数组的小数和为1 (13) (1) (1342) 16 主要思路 在归并排序两两比较两个数组的元素时就确定对应的小数和具体做法是分析当前数是另一个数组中多少个数的小数即当前数多少次被用于计算小数和 #include iostream
#include vectorclass Solution{
public:int Merge_Sort(std::vectorint arr){if(arr.size() 1) return 0;int sum split(arr, 0, arr.size() - 1);return sum;}// 二分int split(std::vectorint 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, mid1, r);int count3 merge(arr, l, mid, mid1, r);// 归并return count1 count2 count3;}int merge(std::vectorint arr, int l1, int r1, int l2, int r2){int sum 0;std::vectorint 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::vectorint 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 vectorclass Solution{
public:int Merge_Sort(std::vectorint arr){if(arr.size() 1) return 0;int sum split(arr, 0, arr.size() - 1);return sum;}// 二分int split(std::vectorint 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, mid1, r);int count3 merge(arr, l, mid, mid1, r);// 归并return count1 count2 count3;}int merge(std::vectorint arr, int l1, int r1, int l2, int r2){int sum 0;std::vectorint 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::vectorint input {7, 5, 6, 4};Solution S1;int res S1.Merge_Sort(input);std::cout res std::endl;return 0;
}
