建设微商城网站,顺德网站建设域名,wordpress头像尺寸,清新区住房和城乡建设部网站目录
归并排序的理论知识
归并排序的实现
merge函数
递归实现
递归改非递归
归并排序的性能分析
题目强化
题目一#xff1a;小和问题
题目二#xff1a;求数组中的大两倍数对数量
题目三#xff1a;LeetCode_327. 区间和的个数 归并排序的理论知识
归并排序小和问题
题目二求数组中的大两倍数对数量
题目三LeetCode_327. 区间和的个数 归并排序的理论知识
归并排序Merge Sort又叫二路归并排序是一种基于分治法并且稳定的排序算法。它先将待排序序列递归地分成两半对两个子序列分别递归排序最后将已排好序的子序列利用归并操作Merge合并为一个整体有序的序列。归并排序的优点在于能够保证稳定性形式上的算法复杂度为O(nlogn)适用于大数据量的排序。大体过程可以概括如下 1. 将待排序的序列对半分为两个子序列。 2. 对两个子序列递归地调用归并排序将其变成两个有序的序列。 3. 将两个已排序的子序列合并成一个有序序列。 例如对一个[1, 9]的区间序列进行归并排序是先将其分为[1, 4] 和 [5, 9]两个序列然后对这两个序列分别进行归并排序递归的过程最后将这两个区间进行merge归并、合并操作。由于是排序好的序列所以merge起来就很方便了先申请一个和[1, 9]范围大小相同的新序列然后将原来的两个数组排序放入新的序列中最后将新的序列从原数组的1位置即左区间边界的位置开始覆盖到9位置即右区间边界的位置。
归并排序的实现
归并排序的函数定义如下
//归并排序
class MergeSort
{
private:void merge(vectorintnums, int l, int mid, int r); //merge函数
public:void RecursionMerge(vectorint nums, int l, int r); //递归版本void IterationMerge(vectorint nums, int n); //迭代版本
};
merge函数
merge函数的时间复杂度为O(N)由于新申请了一个数组所以空间复杂度也是O(N)的。其中N的大小为 r-l1 。注意merge函数的使用前提是要保证左右两个区间都是有序的。
void MergeSort::merge(vectorint nums, int l, int mid, int r)
{//边界控制if (l r || mid r)return;//先申请一个新数组vectorint temp;int i l, j mid 1;//当两个区间都没走到头的情况while (i mid j r){int min nums[i] nums[j] ? nums[i] : nums[j];temp.push_back(min);}//当有一个区间走到头另一个区间直接复制过去就好了//下面两个while循环一定只会执行一个while (i mid j r){temp.push_back(nums[j]);}while (j r i mid){temp.push_back(nums[i]);}//将新申请的数组覆盖到原数组的左区域边界lcopy(temp.begin(), temp.end(), nums.begin() l);
}
递归实现
merge函数写好之后归并排序的递归写法就比较简单了。先递归地将左右区间归并排序然后最后再将这两个排序好的区间序列合并起来。具体的代码实现如下
void Sort::MergeSort::RecursionMerge(vectorint nums, int l, int r) //递归版本
{//base caseif (l r)return;//normal caseint mid l (r - l) / 2;RecursionMerge(nums, l, mid);RecursionMerge(nums, mid 1, r);merge(nums, l, mid, r);
}
递归改非递归
递归改非递归的核心思路就是将原来的递归过程拆分为迭代通过手动迭代的方式模拟实现和原来递归的相同功能。
具体的做法是设一个步长step这和希尔排序有点类似然后以step为区间大小划分左右区间。即从头到尾对每一个 2*step 大小的区间进行归并排序。直到走到不能以step为大小将后续区间分成左右两个区间为止即left小于nleft是在从头到尾的过程中不断变化的
然后从头到尾来一遍之后使setp的值乘2继续从头到尾来一遍直到step的值小于待排序数组的大小n为止。具体的代码实现如下
void MergeSort::IterationMerge(vectorint nums, int n)
{int step 1;while (step n){int left 0;while (left n){int mid left step - 1, right min(n - 1, mid step);merge(nums, left, mid, right);left right 1;}//范围检查防止int溢出if (step INT_MAX / 2)break;step * 2;}
}
归并排序的性能分析
由于merge函数的时间复杂度和空间复杂度都是O(N)级别的所以归并排序的时间复杂度为O(NlogN)空间复杂度为O(N)因为时间是不断累加的空间是取最大的一次。
而且归并排序是三个时间复杂度O(NlogN)级别中唯一的一个有稳定性的排序但同时也是额外空间复杂度最大的一个(快排为O(logN)堆排是O(1)的)。
题目强化
归并排序还有一个应用场景就是对于要找一个数组中所有数的左边有多少个符合特定条件的数可以将原本的O(N²)时间复杂度降低为O(logN)的时间复杂度。 例如假设有这样一个数组arr[1, 2, 3, 4, 5, 6, 7, 8] 当递归到最底层时分组为[1, 2]、[3, 4]、[5, 6]、[7, 8] 那么此时第一组的左组为[1]右组为[2]第二组的左组为[3]右组为[4]……以此类推。 当这一次的merge结束之后数组的分组情况为 [1, 2, 3, 4]、[5, 6, 7, 8] 那么此时第一组的左组就为[1, 2]右组为[3, 4]…… 可以看到上一次的整个第一组已经变成了第二次的左组那么将[1]作参考的话之前的[2]是它的右组其求的是[2]这个范围的目标值而第二次求的就是[3. 4]这个范围的目标值。所以如果只看[1]这个数的话从最底层的merge到最后的merge他就是相当于分步去求了[2]~[8]这些范围的所有目标值。即其右边所有的目标值。 而对于[2]这个数由于其第一次是做的右组而且它永远要么是它前面数的右组要么和前面的数一起做左组。所以同理对于[2]这个数从最底层的merge到最后一次merge他也是相当于找到了[2]右边所有的目标值。 所以通过上面的过程我们可以发现利用归并排序我们将一个数右边所有符合条件的目标值都找到了而且每个数之间只匹配了一次并没有赘余或者重复。 而且将原来O(N(N1)/2)时间复杂度的任务变成了现在O(N*logN)级别的任务。 那么如果我们想要找一个数左边所有的符合某一条件的数呢我们可以试着用逆序排序的方式或者从在左组将原本从左往右变成内从右往左。 如果还不理解可以结合下面的题目来理解。
题目一小和问题
题目描述: 在一个数组中一个数左边比它小的数的总和叫数的小和所有数的小和累加起来叫数组小和。求数组小和。 例子 [1,3,4,2,5] 1左边比1小的数没有 3左边比3小的数1 4左边比4小的数1、3 2左边比2小的数1 5左边比5小的数1、3、4、 2 所以数组的小和为1131134216 思路点拨 由于这题是求数组的小和并不是求每一个数组元素对应的小和。所以反正最后是求出一个和。那么我们转换思路求数组的小和并不一定非要求出每一个数组元素左边所有比它小的数的总和。可以试着求出每一个元素所有右边比它大的数然后数目乘自身的值这样也是数组的小和。 我的题解
#include iostream
#include algorithm
using namespace std;#define TEMPSIZE 5 // 数组暂定大小template typename T
class printVal
{
public:void operator()(T val){cout val ;}
};
class lessSum // 小和问题
{/*题目描述在一个数组中一个数左边比它小的数的总和叫数的小和所有数的小和累加起来叫数组小和。求数组小和。例子[1,3,4,2,5]1左边比1小的数没有3左边比3小的数14左边比4小的数1、32左边比2小的数15左边比5小的数1、3、4、 2所以数组的小和为1131134216思路分析由于这题是求数组的小和并不是求每一个数组元素对应的小和。所以反正最后是求出一个和。那么我们转换思路求数组的小和并不一定非要求出每一个数组元素左边所有比它小的数的总和。可以试着求出每一个元素所有右边比它大的数然后数目乘自身的值这样也是数组的小和。*/
private:void base_merge(int *nums, int l, int m, int r); // 将l ~ m与m1 ~ r范围的有序数组合并int merge(int *nums, int l, int m, int r);public:void mergeSortMode(int *nums, int n);int solution(int *nums, int l, int r);
};int main()
{int nums[TEMPSIZE] {1, 3, 4, 2, 5};// lessSum().mergeSortMode(nums, 5);cout lessSum().solution(nums, 0, 4) endl;for_each(nums, nums TEMPSIZE, printValint());return 0;
}void lessSum::mergeSortMode(int *nums, int n)
{int step 1;while (step n){int mid 0, left 0, right 0;while (left n){mid left step - 1, right std::min(mid step, n - 1);merge(nums, left, mid, right);left right 1;}step * 2;}
}
int lessSum::solution(int *nums, int l, int r)
{if (l r)return 0;int mid l (r - l) / 2;return solution(nums, l, mid) solution(nums, mid 1, r) merge(nums, l, mid, r);
}
int lessSum::merge(int *nums, int l, int mid, int r)
{if (l r)return 0;int ans 0, n r - l 1;int tmp[TEMPSIZE] {0}, index 0;int i l, j mid 1; // i-左组区域j-右组区域while (i mid j r){//要保持i位置严格小于j位置因为要保证先拷贝右组数据ans nums[i] nums[j] ? nums[i] * (r - j 1) : 0;tmp[index] nums[i] nums[j] ? nums[i] : nums[j];}if (i mid 1){copy(nums j, nums r 1, tmp index);}if (j r 1){copy(nums i, nums mid 1, tmp index);}copy(tmp, tmp n, nums l);cout l r ans endl;return ans;
}
void lessSum::base_merge(int *nums, int l, int m, int r)
{if (l r)return;int size r - l 1;int tmp[TEMPSIZE] {0};int i l, j m 1, index 0;while (i m j r)tmp[index] nums[i] nums[j] ? nums[i] : nums[j];if (i m 1)copy(nums j, nums r 1, tmp index);if (j r 1)copy(nums i, nums m 1, tmp index);copy(tmp, tmp size, nums l);
}
题目二求数组中的大两倍数对数量
题目描述 求给定数组中特定的元素的对数。 特定元素-在num的右边有多少个数它的二倍还没有num大。返回总对数。 思路点拨 我们假定归并排序是按照升序排的那么每次merge的时候左右组中的数据都是升序排序好的所以我们找count的时候就不用一个一个数了如果右组right中的当前数还没有当前左组的数left大那么在right之前的数的二倍也一定都没有left大所以此时的count值就可以直接加上一个 右组的大小size - 右组当前位置right的下标。 我的题解
#include iostream
#include vector
#include algorithm
using namespace std;class solution
{
private:int merge(vectorint nums, int l, int mid, int r);public:int mytry(vectorint nums, int l, int r){if (l r)return 0;int mid l (r - l) / 2;int left mytry(nums, l, mid);int right mytry(nums, mid 1, r);int now merge(nums, l, mid, r);return left right now;}
};
int solution::merge(vectorint nums, int l, int mid, int r)
{if (l r)return 0;int edgeR mid 1, count 0;//枚举求countfor (int i l; i mid; i){while (edgeR r nums[i] nums[edgeR] * 2 edgeR);count r - edgeR 1;}// 归并部分vectorint tmp;int i l, j mid 1;while (i mid j r){tmp.push_back(nums[i] nums[j] ? nums[i] : nums[j]);}while (i mid j r)tmp.push_back(nums[j]);while (j r i mid)tmp.push_back(nums[i]);copy(tmp.begin(), tmp.end(), nums.begin() l);//返回countreturn count;
}
int main()
{// 数据[6, 7, 3, 2, 1] ans6vectorint nums {6, 7, 2, 3, 1};cout solution().mytry(nums, 0, nums.size() - 1) endl;return 0;
}
题目三LeetCode_327. 区间和的个数
题目描述 给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中值位于范围 [lower, upper] 包含 lower 和 upper之内的 区间和的个数 。 区间和 S(i, j) 表示在 nums 中位置从 i 到 j 的元素之和包含 i 和 j (i ≤ j)。 示例 1 输入nums [-2,5,-1], lower -2, upper 2 输出3 解释存在三个区间[0,0]、[2,2] 和 [0,2] 对应的区间和分别是-2 、-1 、2 。 示例 2 输入nums [0], lower 0, upper 0 输出1 提示 1 nums.length 105 -231 nums[i] 231 - 1 -105 lower upper 105 题目数据保证答案是一个 32 位 的整数 来源力扣LeetCode 链接https://leetcode.cn/problems/count-of-range-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 思路点拨 首先我们假定从 i 到 j 范围的区间和表示为 S(i, j)那么S(i, j)就可以等价转换为 S(i, j) S(0, j) - S(0, i) 所以我们可以搞一个前缀和数组Sum数组中每一个元素对应的就是当前的S(0, index)。 那么如果S(i, j)的范围是 [lower, upper]的话就表示Sum[j] - Sum[i]的范围就是 [lower, upper]即 lower Sum[j] - Sum[i] upper那么转换一下就是 Sum[j] - upper Sum[i] Sum[j] - lower 这就表示在Sum数组中如果当前位置为 j 对应的前缀和为Sum[j]那么就相当于在Sum数组中找在 j 的左边有多少Sum[i]符合 Sum[j] - upper Sum[i] Sum[j] - lower。 到了这里就对上了“找一个数左边所有符合条件数的个数”的情形只不过这里我们需要将原数组处理成前缀和数组Sum然后对这个Sum数组进行操作而不是对原数组进行操作。 我的题解
#includeiostream
#includevector
#includestring
#includelist
#includealgorithm
using namespace std;class Solution
{
public:int merge(vectorlong sum, int l, int mid, int r, int lower, int upper){// 由于左组和右组都是有序的所以巧妙的实现了指针不用回退// 这里的i对应“思路点拨”部分的jint cnt 0;int l_edge l, r_edge l; for (int i mid 1; i r; i){long tagL sum[i] - upper, tagR sum[i] - lower;while (sum[r_edge] tagR r_edge mid) // 走到第一个大于tagR的位置r_edge;while (sum[l_edge] tagL l_edge mid) // 走到第一个不小于tagL的位置l_edge;//由于r_edge是在第一个大于tagR的位置所以sum的区间为(L,R]故最终减去l_edge的结果就不用再1了cnt r_edge - l_edge 0 ? r_edge - l_edge : 0; }// 正常的mergevectorlong temp;int i l, j mid 1;while (i mid j r){temp.push_back(sum[i] sum[j] ? sum[i] : sum[j]);}while (i mid j r){temp.push_back(sum[j]);}while (j r i mid){temp.push_back(sum[i]);}copy(temp.begin(), temp.end(), sum.begin() l);// 返回当前区间值位于范围 [lower, upper] 的区间和return cnt;}int sumCount(vectorlong sum, int l, int r, int lower, int upper){if (l r)return sum[l] lower sum[r] upper;int mid (l r) / 2;return sumCount(sum, l, mid, lower, upper) sumCount(sum, mid 1, r, lower, upper) merge(sum, l, mid, r, lower, upper);}int countRangeSum(vectorint nums, int lower, int upper){// 填充sum序列其中S(i,j) S(0,j) - S(0,i) vectorlong sum; // sum数组比nums大1sum.push_back(nums[0]);for (int i 1; i nums.size(); i){sum.push_back(sum[i - 1] nums[i]);}//返回符合条件区间和的数量return sumCount(sum, 0, sum.size() - 1, lower, upper);}
};int main()
{auto pt [](const int val){ cout val ; };vectorint nums { -2, 5, -1 };for_each(nums.begin(), nums.end(), pt);cout endl;cout Solution().countRangeSum(nums, -2, 2);return 0;
}
