分治—快排与归并算法的学习与习题

目录1.快速排序1.1颜色分类1.2排序数组1.3数组中第K个最大元素1.4库存管理III2.归并排序2.1排序数组2.2交易逆序对的总数2.3计算右侧小于当前元素的个数2.4翻转对1.快速排序这里使用的快速排序是三路快排先简单介绍一下快速排序的思路对于每次排序选定一个基准值根据这个基准值对当前区间的元素进行排序假设使用升序的方法那么基准值左侧全部小于key基准值右侧全部大于key中间的部分是值均为key的一段数组那么此时数组整体来看是有序的左侧小右侧大只不过左右区间内部还不是有序的所以要进一步递归进入左右数组继续使用快排这就是三路快排的思路因为加入了一个等于key的区间这使得如果数组内部有大量重复数据时的时间复杂度大大减小假设一个数组全部都是一个值那么就会得到最大的遍历次数对于普通快排每次遍历的元素个数递减n(n-1)(n-2)..21得到O(n^2)的时间复杂度但是加上了中间这个区间只需要遍历n次即可将全部元素相同的这个数组排好1.1颜色分类75. 颜色分类 - 力扣LeetCode对于这样的数组其实就是选定基准值为1将数组进行三路快排这里要用到三个指针一个指针控制左侧的小区间一个指针控制右侧的大区间一个指针用于遍历数组因为左侧小右侧大所以我们将左指针left设为-1右指针right设为num.size()在数组边界待命然后从0开始遍历数组使用i遍历如果碰到的元素小于key那么把元素丢到左侧并让i注意把元素丢到左侧前要先left如果等于key就让i即可如果大于key那么将元素丢到右侧但是注意我们从左向右扫描整个数组i与left之间的元素都应该是key但是对于右侧未扫描的元素我们无法确定交换过来的元素和key的关系所以i不能移动要进行下一轮的判断代码部分class Solution { public: void sortColors(vectorint nums) { int left-1; int rightnums.size(); int ileft1; while(iright){ if(nums[i]1)swap(nums[left],nums[i]);//左侧已经扫描过交换的元素不用再次检查 else if(nums[i]1)nums[i]; else swap(nums[--right],nums[i]);//右侧没扫描i不动 } return; } };1.2排序数组912. 排序数组 - 力扣LeetCode这道题就是上一题的进阶上一次由于只有三种数据选定中间值作为基准值遍历一边即可完成排序而对于普通的数组进行排序每次都要选定一个随机元素作为基准值因为随机出的基准值可以让排序效率稍微高一点这里就需要使用到rand函数和srand函数主函数使用时间戳的数据作为种子让rand函数可以真正随机出数字让rand的结果%上区间的长度再加上左端点的下标即可得到当前区间的随机基准值其他部分没有难点只不过就是对左右数组进一步递归快排代码部分将代码拆分成几个函数部分getRandom用于取出每个区间的基准值将快排的实现操作放在myqsort中注意最后划分的区间是[l,left][left1,right-1][right,r]这是下一次排序的区间划分注意如果传入的左右端点重合了说明区间只有一个元素直接返回即可class Solution { public: vectorint sortArray(vectorint nums) { srand(time(NULL)); int left -1; int right nums.size(); int i left 1; myqsort(nums, left 1, right - 1); return nums; } int getRandom(vectorint nums, int l, int r) { int pos rand() % (r - l 1) l; return nums[pos]; } void myqsort(vectorint nums, int l, int r) { if(lr)return; int k getRandom(nums, l, r); int left l - 1; int right r 1; int i left 1; while (i right) { if (nums[i] k) swap(nums[left], nums[i]); else if (nums[i] k) nums[i]; else swap(nums[--right], nums[i]); } //[l,left][left1,right-1][right,r] myqsort(nums, l, left); myqsort(nums, right, r); return; } };1.3数组中第K个最大元素215. 数组中的第K个最大元素 - 力扣LeetCode这道题在每次排序前需要根据区间长度判断这个元素在哪个区间对于划分出的三个区间abca区间大于基准值b区间等于基准值c区间小于基准值假如aK说明该元素应该存在于a区间假如abK说明满足Ka那么此时b区间的基准值就是第K个最大元素而如果Kab此时K就落在c区间所以只需要对目标区间继续排序查找即可对于c区间K要变成K-a-b再进行排序因为排除了右侧的ab个元素那么相当于在c区间查找第K-a-b大的元素代码部分class Solution { public: int findKthLargest(vectorint nums, int k) { srand(time(NULL)); return myqsort(nums,0,nums.size()-1,k); } int getRandom(vectorint nums,int l,int r){ return nums[rand()%(r-l1)l]; } int myqsort(vectorint nums,int l,int r,int k){ if(lr)return nums[l]; int posgetRandom(nums,l,r); int leftl-1; int rightr1; int ileft1; while(iright){ if(nums[i]pos)swap(nums[left],nums[i]); else if(nums[i]pos)nums[i]; else swap(nums[--right],nums[i]); } int ar-right1; int bright-left-1; int cleft-l1; if(ak)return myqsort(nums,right,r,k); else if(abk)return pos; else return myqsort(nums,l,left,k-a-b); }1.4库存管理IIILCR 159. 库存管理 III - 力扣LeetCode和上一次的思路类似只不过这次要返回区间但是这反而更简单了因为对于区间内部不需要有序也不用定位到精确的元素同样是这幅图这次只需要将右侧作为小的那一侧进行排序即可然后就是对区间长度进行判断假如acnt说明区间在a内部为什么不带等号呢因为如果acnt那么直接返回a区间就行假如abcnt说明区间的左端点在b区间只要从右侧向左找cnt个元素即可假如cntab说明左端点在c区间注意仍然需要对cnt进行更改代码部分class Solution { public: vectorint inventoryManagement(vectorint stock, int cnt) { srand(time(NULL)); vectorint ret; int lenstock.size(); myqsort(stock,0,len-1,cnt); for(int i1;icnt;i){ ret.push_back(stock[len-i]); } return ret; } int getRandom(vectorint stock,int l,int r){ return stock[rand()%(r-l1)l]; } int myqsort(vectorint stock,int l,int r,int cnt){ if(lr)return l; int posgetRandom(stock,l,r); int leftl-1; int rightr1; int ileft1; while(iright){ if(stock[i]pos)swap(stock[left],stock[i]); else if(stock[i]pos)stock[i]; else swap(stock[--right],stock[i]); } int ar-right1; int bright-left-1; int cleft-l1; if(acnt)return myqsort(stock,right,r,cnt); else if(abcnt)return cnt; else return myqsort(stock,l,left,cnt-a-b); } };2.归并排序归并排序就是将数组先分割到最小然后逐次向上返回逐渐合并小区间每次合并时左右区间应当都有序然后依次将数组元素按顺序合并这里要借助一个辅助的数组存储合并的结果并映射到原数组将原数组的这部分进行更改从底下的最小数组逐层向上合并2.1排序数组912. 排序数组 - 力扣LeetCode刚才用快排解决了问题这次用归并的方法核心就是这一部分代码每次进入归并如果左右端点重合就直接返回如果还可以继续分割数组就继续递归这里不使用基准值而是直接将数组对半分开每个区间都对半分开然后往下递归到最下层的时候也就是找到了最左侧的两个元素此时开始第一次的合并因为只有一个元素所以左右数组已经有序然后用指针遍历两个数组按照小的先进放入临时数组然后将排序结果映射到原数组注意当元素多起来的时候左右数组可能存在当一个数组已经走完另一个数组还剩下元素的情况要将剩下元素全部放入临时数组注意最后的for循环因为j是从左端点移动到右端点是原数组实际的下标而临时数组是从0开始的要注意下标的控制代码部分class Solution { public: vectorint sortArray(vectorint nums) { vectorint tmp(nums.size()); mymergesort(nums,0,nums.size()-1,tmp); return nums; } void mymergesort(vectorint nums,int l,int r,vectorint tmp){ if(lr)return; int mid(lr)/2; //[l,mid][mid1,r]把数组分为两部分继续归并 mymergesort(nums,l,mid,tmp); mymergesort(nums,mid1,r,tmp); int cur1l; int cur2mid1; int i0; while(cur1midcur2r){ if(nums[cur1]nums[cur2])tmp[i]nums[cur1]; else tmp[i]nums[cur2]; } while(cur1mid)tmp[i]nums[cur1]; while(cur2r)tmp[i]nums[cur2]; for(int jl;jr;j){ nums[j]tmp[j-l]; } return; } };2.2交易逆序对的总数LCR 170. 交易逆序对的总数 - 力扣LeetCode这道题的逆序对可以逐层拆解也就是对于我们拆开的左右数组每次的左右区间内部都已经查找完了逆序对并且有序在合并时查找新的逆序对从左边挑一个从右边挑一个组成逆序对至于为什么我们可以设定左右区间内部有序且查找完逆序对再往上合并因为当数组分割到只剩一个元素自然就满足了条件因为一个元素必定有序且逆序对已经找完只不过逆序对为0然后向上返回开始左右区间的合并与新的逆序对查找这里使用升序排序将右数组作为主数组左数组用于累加结果因为逆序对左边大所以当左侧的record[cur1]record[cur2]时由于数组升序所以cur1以及右侧所有元素都和当前cur2位置的元素构成逆序对且因为是新数组合并必然不重复并且可以大大提高查找速度也就是逆序对个数right-cur11一次性可以找一串代码部分其实代码部分需要改动的不多啊基本上都是归并排序需要写的基本步骤只不过在小的判断条件上小小更改一下就可以了class Solution { public: int reversePairs(vectorint record) { vectorint tmp(record.size()); int ret0; mymsort(record,0,record.size()-1,ret,tmp); return ret; } void mymsort(vectorint record,int left,int right,int ret,vectorint tmp){ if(leftright)return; int mid(leftright)/2; mymsort(record,left,mid,ret,tmp); mymsort(record,mid1,right,ret,tmp); int cur1left; int cur2mid1; int i0; while(cur1midcur2right){ if(record[cur1]record[cur2])tmp[i]record[cur1]; else{ ret(mid-cur11); tmp[i]record[cur2]; } } while(cur1mid)tmp[i]record[cur1]; while(cur2right)tmp[i]record[cur2]; for(int jleft;jright;j){ record[j]tmp[j-left]; } return; } };2.3计算右侧小于当前元素的个数315. 计算右侧小于当前元素的个数 - 力扣LeetCode这道题和上一题的思路类似只不过这里我们换一个思路使用降序然后从前一个数组中取大的元素也就是将左数组作为主数组从右数组中累加结果如果是升序假设此时cur1的位置元素比cur2要大因为是升序只知道cur2以及左侧元素均小于cur1的元素但是此时cur2进行移动之后新的元素是不是一定比cur1位置的小呢这是未知的也就是不能一次性确定一串满足条件的元素个数进行累加也就是这次判断对累加结果没有作用但是使用降序的话同样的情况可以确定cur2以及右侧元素一定是比cur1位置元素小的所以主数组的选择对升降序的要求也不一样注意这道题要返回的是一个数组每个位置对应多少个结果要一一返回出来这就需要多一个辅助数组用于绑定每一个元素的下标只要每次合并数组时对下标数组也进行一样的操作就可以通过元素获取到它本来的下标因为最终的返回数组是按照最开始没有排序的位置给每个位置加上对应满足元素的个数所以记录原下标是很有必要的代码部分代码部分看着很多其实需要注意细节的地方就那么几个大部分依旧是归并的基础代码这里只是加上了对下标数组的同步操作注意辅助数组也要多加一个vectorint tmp1(100005); vectorint tmp2(100005); class Solution { public: vectorint countSmaller(vectorint nums) { int len nums.size(); vectorint index(len); vectorint result(len); for (int i 0; i len; i) { index[i] i; } // 三个数组tmp用于归并的临时数组 // index绑定元素和下标 // result是结果数组 mymsort(nums, 0, len - 1, index, result); return result; } void mymsort(vectorint nums, int left, int right, vectorint index, vectorint result) { if (left right) return; int mid (left right) / 2; mymsort(nums, left, mid, index, result); mymsort(nums, mid 1, right, index, result); int cur1 left; int cur2 mid 1; int i 0; while (cur1 mid cur2 right) { if (nums[cur1] nums[cur2]) { tmp1[i] nums[cur1]; tmp2[i] index[cur1]; result[index[cur1]] (right - cur2 1); //通过下标数组定位位置 i; cur1; } else { tmp1[i] nums[cur2]; tmp2[i] index[cur2]; i; cur2; } } while (cur1 mid) { tmp1[i] nums[cur1]; tmp2[i] index[cur1]; i; cur1; } while (cur2 right) { tmp1[i] nums[cur2]; tmp2[i] index[cur2]; i; cur2; } for (int j left; j right; j) { nums[j] tmp1[j - left]; index[j] tmp2[j - left]; } return; } };2.4翻转对493. 翻转对 - 力扣LeetCode这道题就是把条件稍微改了一下将逆序对的条件改成了大于两倍才行代码部分需要改动的不多对于左右的有序数组遍历两次即可第一次累加翻转对的对数但是对数组不进行合并因为这个条件如果直接拿去排序不能保证新数组有序所以我们将找翻转对和合并数组分两步进行即可代码部分vectorint tmp(50005); class Solution { public: int reversePairs(vectorint nums) { int len nums.size(); int ret 0; mymsort(nums, 0, len - 1, ret); return ret; } void mymsort(vectorint nums, int left, int right, int ret) { if (left right) return; int mid (left right) / 2; mymsort(nums, left, mid, ret); mymsort(nums, mid 1, right, ret); int cur1 left; int cur2 mid 1; int i 0; while (cur1 mid cur2 right) { if (nums[cur1]/2.0 nums[cur2]) { ret (right - cur2 1); cur1; } else cur2; } cur1 left; cur2 mid 1; while (cur1 mid cur2 right) { if (nums[cur1] nums[cur2]) { tmp[i] nums[cur1]; } else tmp[i] nums[cur2]; } while (cur1 mid) tmp[i] nums[cur1]; while (cur2 right) tmp[i] nums[cur2]; for (int j left; j right; j) { nums[j] tmp[j - left]; } return; } };