会向耀灵淬天剑剑拔飞刃斩仇雠。欢迎来到丘山望岳的小栈今天分享分治算法从熟络的快排归并讲起话不多说我们现在发车。分治思想把大问题拆成多个相同的小问题分别求解再把小结果合并得到原问题答案就是分治。——沃茨基硕德一、快速排序快速排序一句话说就是每次执行一次排序就会选择一个数把它放置在一个位置这个数在后面的每次排序中都不会变化位置也就是说当一个数被放置在这个位置之时这个位置就是把整个数列排序后这个数处在的位置。那么这个算法是如何实现的呢每次排序以升序为例都选择一个元素通过一系列算法操作把小于它的数放置在左边大于它的数放置在右边当然这个元素左右两边的数不一定有序。每次排序之后再把除这个元素之外的其他元素经行排序具体操作就是使用递归思想把这个元素左边右边的元素分为两个子序列再对其经行排序。直到每次排序时的数列元素只有一个就可以终止递归。一次快速排序举例[5, 2, 9, 3, 7, 6, 1, 8]- [1, 2, 3, 5, 7, 6, 9, 8]你看选取元素5作为基准大于5的元素有4个不定序放置在5的右边小于5的元素有3个不定序放置在5的左边5在这个序列中是第4小的数小于5的3个元素刚好放置在5的左边5经过一趟快速排序放置在了数组的第四位此后排序它的位置都不会改变了。之后再对[1,2,3] ,[7,6,9,8]两个序列数组经行排序快排实现之三路划分1.1三路划分思想三路划分思想是利用三指针将只有三种元素的数组按照元素种类分为三块下面是一道题目高度凝练了这种算法思想75. 颜色分类https://leetcode.cn/problems/sort-colors/算法思想解析使用三指针一个”指针“用于遍历另外两个“指针”用于将数组一分为三在遍历过程中数组为【0left】全是零的区域【left1,i】全是1的区域【i1,right-1】待扫描的区域【right,end】全是2的区域整个算法的思想就像把一堆红豆绿豆黑豆混合物分类是红豆放在左边成一堆是绿豆放在右边成一堆当原来豆堆中只剩下黑豆的时候分类完成。所以遍历的元素nums[i]1.是0,通过left来扩充是0的区间但此时left指向的元素是1i指向的元素是0所以二者交换i指向元素是1i遍历下一个元素。2.是1i扩充全是1的区间长度并遍历下一个区间3.是2 right--扩充全是2的区间长度此时right指向一个没有被遍历到的元素不确定是01还是2i指向2nums[i] nums[right] 交换但由于此刻交换后指向是一个没有被遍历的元素i不能还要继续遍历这个元素。当iright时结束循环class Solution { public: void sortColors(vectorint nums) { int left-1,rightnums.size(),i0; while(iright) { if(nums[i]0)swap(nums[left],nums[i]); else if(nums[i]1)i; else swap(nums[--right],nums[i]); } } };1.2快排三步走通过上面的讲解我们知道快排的三个步骤1.选取基准元素2.把比基准元素小的元素放在基准元素左边把比基准元素大的元素放在基准元素的右边3.左右子区间递归排序1.3基于三路划分思想实现快速排序快排的第一步是要选择基准元素我们可使用随机数的方式在指定数组范围中选出一个随机元素之后结合快排思想和三路划分思想将数组基于指定元素的大小分为小于等于大于三块再将小于大于这个基准元素的部分再次递归调用排序直到每个子数组只有一个元素为止。代码实现class Solution { public: int getKey(int left,int right,vectorintnums) { int lenright-left1; return nums[rand()%lenleft]; } void qsort(int left,int right,vectorintnums) { if(leftright)return ; int keygetKey(left,right,nums); int lleft-1,rright1,ileft; while(ir) { if(nums[i]key)swap(nums[l],nums[i]); else if(nums[i]key)swap(nums[--r],nums[i]); else i; } qsort(left,l,nums); qsort(r,right,nums); } vectorint sortArray(vectorint nums) { srand(time(NULL)); qsort(0,nums.size()-1,nums); return {nums.begin(),nums.end()}; } };注意递归终止条件 if(leftright)包含数组元素只含一个或不含任何元素。二、快速选择算法215. 数组中的第K个最大元素https://leetcode.cn/problems/kth-largest-element-in-an-array/算法分析采用快速选择算法——本质快排在达到解决问题目标但是数组还没完全有序时终止排序。首先使用三路划分随机选取基准排降序由于快排的特性每次快排挑出一个元素放置在一个位置之后这个元素的位置都不会再改变。计算 基准之间的长度为 a ,b ,c 区间是前a大的数但是是乱序区间的元素都排到了它们应该在的位置区间就是余下的元素都是乱序的当ak时继续在区间寻找元素复用快速选择逻辑将k大的元素排放在它应该在的位置。当abk时第k大的元素已经在它应该在的位置了终止算法其余情况复用快速选择逻辑在区间排第k-a-b大的元素使之在应该在的位置上class Solution { public: int findKthLargest(vectorint nums, int k) { int nnums.size(); srand(time(NULL)); qsort(0,n-1,nums,k); return nums[k-1]; } void qsort(int l,int r,vectorint nums,int k) { if(lr)return ; int keyget_key(l,r,nums); int leftl-1,rightr1,il; while(iright) { if(nums[i]key)swap(nums[i],nums[left]); else if(nums[i]key)i; else swap(nums[i],nums[--right]); } int aleft-l1,bright-1-left; if(ak)qsort(l,left,nums,k); else if(abk)return ; else qsort(right,r,nums,k-a-b); } int get_key(int l,int r,vectorint nums) { int lenr-l1; return nums[lrand()%len]; } };下面是一个题目来强化一下LCR 159. 库存管理 IIIhttps://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/class Solution { public: vectorint inventoryManagement(vectorint nums, int k) { int nnums.size(); srand(time(NULL)); qsort(0,n-1,nums,k); return {nums.begin(),nums.begin()k}; } void qsort(int l,int r,vectorint nums,int k) { if(lr)return ; int keyget_key(l,r,nums); int leftl-1,rightr1,il; while(iright) { if(nums[i]key)swap(nums[i],nums[left]); else if(nums[i]key)i; else swap(nums[i],nums[--right]); } int aleft-l1,bright-1-left; if(ak)qsort(l,left,nums,k); else if(abk)return ; else qsort(right,r,nums,k-a-b); } int get_key(int l,int r,vectorint nums) { int lenr-l1; return nums[lrand()%len]; } };三、归并排序归并排序的思想很简单就是将一个数列打散成单个元素再首先两两合并成元素个数为2的数组也可能为1数组元素个数为奇数有一个元素落单再两两合并成元素个数为4的数组也有可能为32有一组落单或有一组元素个数为1依次合并合并成原数组。代码实现过程思想两个有序数组的合并88. 合并两个有序数组https://leetcode.cn/problems/merge-sorted-array/算法原理双指针使用两个“指针”遍历两个数组按照一定要求比如优先安置较小的元素或优先安置较大的元素具体逻辑详见代码class Solution { public: void merge(vectorint nums1, int m, vectorint nums2, int n) { vectorint ret(mn); int ptr10,ptr20,i0; int end1m-1,end2n-1; while(ptr1end1ptr2end2) { if(nums1[ptr1]nums2[ptr2])ret[i]nums1[ptr1]; else ret[i]nums2[ptr2]; } while(ptr1end1)ret[i]nums1[ptr1]; while(ptr2end2)ret[i]nums2[ptr2]; for(int i0;imn;i) nums1[i]ret[i]; } };有了这个算法的加持我们就可以轻而易举地实现归并排序了class Solution { public: vectorint sortArray(vectorint nums) { merge(0,nums.size()-1,nums); return {nums.begin(),nums.end()}; } void merge(int left,int right,vectorintnums) { if(leftright)return ; int midleft(right-left)/2; merge(left,mid,nums); merge(mid1,right,nums); vectorint temp(right-left1); int begin1left,begin2mid1; int end1mid,end2right; int iright-left; while(end1begin1end2begin2) { if(nums[end1]nums[end2])temp[i--]nums[end1--]; else temp[i--]nums[end2--]; } while(end1begin1)temp[i--]nums[end1--]; while(end2begin2)temp[i--]nums[end2--]; for(int i0;iright-left1;i) nums[ileft]temp[i]; } };四、归并算法LCR 170. 交易逆序对的总数https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/算法思想将数组分两半A,B,所求逆序对就是A中的逆序对数B中的逆序对数A,B中各取一个元素组成逆序对数A中逆序对数怎么求继续将之分为两半CD所求即C中的逆序对数D中的逆序对数C,D中各取一个元素组成逆序对数C的逆序对数怎么求……直到将数组分为一系列单个元素。单次算法求解两个子数组中各自抽取一个元素组成逆序对的对数由于是数组问题可以根据单调性利用双指针这个思想的第一步就是排序可以将两个同级子数组如AB排序利用双指针来统计逆序对数。策略一数组排升序逐个固定指向B的指针在A中找一个比B指针指向元素要大的值策略2数组排降序逐个固定指向A的指针在B中找一个比A指针指向元素还要小的值当然每次这样的操作之前要使用递归调用得知两个元素都在A(B)中的逆序对的个数再把数组排序排序的逻辑和归并排序是一样的。代码演示以策略一为例class Solution { public: int cul_rev(vectorint nums,int left,int right) { if(leftright)return 0; int midleft(right-left)/2; int retcul_rev(nums,left,mid)cul_rev(nums,mid1,right); sort(nums.begin()left,nums.begin()mid1); sort(nums.begin()mid1,nums.begin()right1); int cur1left,cur2mid1; while(cur1midcur2right) { if(nums[cur1]nums[cur2])cur1; else { retmid-cur11; cur2; } } sort(nums.begin()left,nums.begin()right1); return ret; } int reversePairs(vectorint record) { if(record.size()0)return 0; return cul_rev(record,0,record.size()-1); } };315. 计算右侧小于当前元素的个数https://leetcode.cn/problems/count-of-smaller-numbers-after-self/和上一题的核心算法思想是一样的只不过需要使用一个映射关系将数组元素和原数组中该元素的位置建立一个映射关系因为上一题思路中排序会改变数组中元素的位置返回的数组是原数组元素所对应的比之小的元素个数是有序且拥有很强的映射关系的。这里有两种思路第一种再使用一个下标数组在排序时原数组元素顺序怎么变下标数组相应变化。第二种使用元素为pair的数组进行算法操作排序归并first是数组元素second是原数组中该元素的下标。class Solution { public: vectorpairint,int temp; vectorpairint,int gen; vectorint ret; vectorint countSmaller(vectorint nums) { int nnums.size(); temp.resize(n); gen.resize(n); ret.resize(n); for(int i0;inums.size();i)gen[i]make_pair(nums[i],i); mergesort(0,n-1); return ret; } void mergesort(int left,int right) { if(leftright)return ; int midleft(right-left)/2; //左右区间排序并统计 mergesort(left,mid); mergesort(mid1,right); //统计”一左一右“并归并排序 int cur1left,cur2mid1,i0; while(cur1midcur2right) { if(gen[cur1].firstgen[cur2].first)temp[i]gen[cur2]; else temp[i]gen[cur1],ret[gen[cur1].second]right-cur21; } while(cur1mid)temp[i]gen[cur1]; while(cur2right)temp[i]gen[cur2]; for(int i0;iright-left1;i) gen[ileft]temp[i]; } };下面这个题目可以当作小练习493. 翻转对https://leetcode.cn/problems/reverse-pairs/代码展示class Solution { public: int ret0; vectorint temp; void fun(int left,int right,vectorint nums) { if(rightleft)return ; int midleft(right-left)/2; //首先计算左右区间翻转对 fun(left,mid,nums); fun(mid1,right,nums); //计算一左一右区间的翻转对 int cur1left; int cur2mid1; while(cur1midcur2right) { //固定cur2逐个找左边较大的元素 if((long long)nums[cur1]((long long)nums[cur2])*2)cur1; else if((long long)nums[cur1]((long long)nums[cur2])*2) retmid-cur11,cur2; } int i0; cur1left; cur2mid1; while(cur1midcur2right) { if(nums[cur1]nums[cur2])temp[i]nums[cur1]; else temp[i]nums[cur2]; } while(cur1mid)temp[i]nums[cur1]; while(cur2right)temp[i]nums[cur2]; for(int i0;iright-left1;i) nums[ileft]temp[i]; } int reversePairs(vectorint nums) { int nnums.size(); temp.resize(n); fun(0,n-1,nums); return ret; } };五、分治思想建模模板总结快排归并排序得到的分治思想分治 递归拆分 基线求解独立子单元 逆向逐级合并拆分原问题分解为若干独立子问题以及后续需要处理的合并任务递归往下切直到子问题足够简单基线条件直接算出独立子问题答案回溯向上把下层子问题的结果通过合并逻辑组装逐层得到上层解。关键点独立子问题负责产生局部结果合并步骤负责处理子单元之间的关联关系这是分治最容易被忽略的部分。 很多人只看到 “拆成小问题”但分治真正的难点不在拆分而在怎么把分散的局部结果联合起来。今天的分享就到此结束啦~感谢各位观众老爷的支持恭祝大家胸有太白浩然气日进陶朱万斗金。