网站的站外推广手段,网站开发的结论,郑州前端培训机构排名,如何写手机app程序总言 主要内容#xff1a;编程题举例#xff0c;理解分治的思想#xff08;主要是对快排、并归的应用#xff09;。 文章目录 总言1、基本介绍2、颜色分类#xff08;medium#xff09;2.1、题解 3、快速排序#xff08;medium#xff09;3.1、题解#xff…
总言 主要内容编程题举例理解分治的思想主要是对快排、并归的应用。 文章目录 总言1、基本介绍2、颜色分类medium2.1、题解 3、快速排序medium3.1、题解三指针版本的快排 4、快速选择算法medium4.1、题解 5、最小的 k 个数medium5.1、题解 6、归并排序medium6.1、题解复习快排二路归并 7、数组中的逆序对hard7.1、题解 8、计算右侧小于当前元素的个数hard8.1、题解 9、翻转对hard9.1、题解 Fin、共勉。 1、基本介绍 分治是一种解决问题的策略它将一个大问题分解成若干个小问题这些小问题与原问题类型相同但规模更小然后递归地解决这些小问题最后将小问题的解合并从而得到原问题的解。这种策略在许多算法中都有应用如排序、搜索、图论问题等。 快速排序就是基于分治策略的一种排序算法。它的基本思想是选取一个基准值通过一趟排序将待排序的数据分割成独立的两部分其中一部分的所有数据都比另一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。快速排序的时间复杂度为O(nlogn)是目前基于比较的内部排序里被认为是最好的方法特别适用于大数据集。 归并排序则是另一种基于分治策略的排序算法。它的主要思路是将两个或两个以上有序表合并成一个新的有序表即把待排序序列分为若干个子序列每个子序列是有序的然后再把有序子序列合并为整体有序序列。归并排序的过程可以分为分解和合并两个步骤分解是将序列每次折半划分合并则是将划分后的序列段两两合并后排序。这种排序算法是稳定的适用于各种规模的数据集。
2、颜色分类medium 题源链接 2.1、题解 1、思路分析 此题的思路本质可划分为双指针双指针复习链接移动零。但对此进行了一点变动使用的是三指针一个用于遍历数组的指针两个用于划分区域的指针。 PS上述指针如何取名完全可随意不必生搬硬套。 如何判断移动 1、初始时 i 0left -1 right numsSize若数组尾元素下标为n-1right指向尾元素下一个位置即n 2、i从左到右遍历过程中 ①、若nums[cur] 0 说明 i 位置指向的元素要纳入左区域范围内。因此交换 left 1 与 i 位置的元素并让 left 因为纳入了新元素 0 序列的右边界应当右滑扩展cur 为什么可以 因为 left 1 位置要么是 0 要么是 1交换完毕之后这个位置的值已经符合我们的要求因此 cur ②、nums[cur] 1 说明这个位置应该在 left 和 cur 之间此时⽆需交换直接让 cur 判断下⼀个元素即可 ③、nums[cur] 2 说明这个位置的元素应该在 right - 1 的位置因此交换 right - 1 与 cur 位置的元素并且让 right-- 指向 2 序列的左边界cur 不变因为交换过来的数是没有被判断过的因此需要在下轮循环中判断 2、题解
class Solution {
public:void sortColors(vectorint nums) {int left -1, right nums.size(), i 0;while(i right)//right表⽰的是2序列的左边界因此当碰到right时说明已经将所有数据扫描完毕了{if(nums[i] 0)swap(nums[i],nums[left]);else if(nums[i] 1)i;else //nums[i] 2swap(nums[i],nums[--right]);//cur 不变因为交换过来的数是没有被判断过的}}
};3、快速排序medium 题源链接 3.1、题解三指针版本的快排 1、思路分析 这题的题解方法有多种这里我们主要学习快排后续讲以同样的题讲解归并。 快排我们在排序章节讲解过几种写法Hoare法、挖坑法、双指针法并且当时对key值的优化使用的是三数取中。这里我们讲解三指针法以及随机数法选取key值。 三指针法 这里三指针的原理同上述颜色分类。 从待排序的数组中选择一个元素作为基准值key以该基准值进行排序将数组划分为左、中 、右三部分以升序为例。 三指针排序的过程在上述颜色分类讲解过这里不做赘述。 在对当前序列进行三块划分处理后再去递归排序左边部分和右边部分即可可以舍去大量的中间部分减少不必要的交换操作。 在处理有大量重复元素的数组时效率会大大提升。 随机数法取key值 在主函数中种一颗随机数种子 由于我们要随机产生一个满足[leftright]区间范围内的基准元素值因此可以将生成随机数转换成为生成当前[leftright]区间的随机下标。如何做到
(rand() % (right -left 1 )) left解释这里我们设区间大小为n让随机数 % 上区间大小可得 [0n-1]范围内的随机数加上区间的左边界即可得到 [left, left (n -1)] 范围内的值即[left, right]区间范围内的值。 2、题解
class Solution {
public:void quick(vectorint nums, int left, int right){if(left right) return; //递归结束条件//随机数法选取key值int n right - left 1;//当前段区间内元素总数int index (rand() % n) left;//获取到[left, right]区间段内的随机下标int key nums[index];//这里不能直接用key的下标进行排序即与nums[index]比较是错误的。//因为快排属于交换排序index下标位置的值会在排序过程中被交换。//三指针法进行区间排序[left,right]int i left, l left - 1, r right 1;while(i r){if(nums[i] key) swap(nums[l],nums[i]);else if(nums[i] key) i;else swap(nums[--r],nums[i]);//交换过来的数是没有被判断过此处i不能}//对左右排序:[left, l] [l1, r-1] [r,right]quick(nums,left,l);quick(nums,r,right);}vectorint sortArray(vectorint nums) {srand(time(nullptr));// 种下⼀个随机数种⼦quick(nums,0,nums.size()-1);//使用递归法排序这里传入[left,right]区间return nums;}
};4、快速选择算法medium 题源链接 4.1、题解 1、思路分析 这题若使用的是选择排序比如直接选择排序或堆排序堆排时间复杂度为 N l o g N NlogN NlogN也可以解决此题
class Solution {
public:int findKthLargest(vectorint nums, int k) {//建堆priority_queueint maxHeap(nums.begin(),nums.end());//取前K-1个数while(--k)//此写法下要用前置自减{maxHeap.pop();}//取第K个数return maxHeap.top();}
};这里我们主要学习应用快排 2、题解 使用升序的写法
class Solution {
public:int qsort(vectorint nums, int k, int left, int right) {if (left right) // 递归调用return nums[left];int n right - left 1; // 当前区间的元素总数int id rand() % n left; // 获取当前区间段的随机下标int key nums[id]; // 获取该下标上的元素值作为key值使用int i left, l left - 1, r right 1;while (i r) // 排升序找第k大。{if (nums[i] key)swap(nums[i], nums[l]);else if (nums[i] key)i;elseswap(nums[i], nums[--r]);}// 用于判断下一轮递归区间:[left,l] [l1,r-1] [r, right]int a l - left 1;int b r - 1 - (l 1) 1;int c right - r 1;if (c k)return qsort(nums, k, r, right);else if (b c k)return key;elsereturn qsort(nums, k - b - c, left, l);}int findKthLargest(vectorint nums, int k) {srand(time(nullptr)); // 种下随机种子return qsort(nums, k, 0, nums.size() - 1); // 传入的区间边界应该是闭区间[left,right]}
};使用降序的写法只是对当前序列的排序部分及判断下一轮递归的条件做了变动。 while (i r) // 排降序找第k大。{if (nums[i] key)swap(nums[i], nums[--r]);else if (nums[i] key)i;elseswap(nums[i], nums[l]);}// 用于判断下一轮递归区间:[left,l] [l1,r-1] [r, right]int a l - left 1;int b r - 1 - (l 1) 1;int c right - r 1;if (a k)return qsort(nums, k, left, l);else if (a b k)return key;elsereturn qsort(nums, k - b - a, r, right);5、最小的 k 个数medium 题源链接 5.1、题解 1、思路分析 此题解法多种可用堆的TOP-K N l o g K NlogK NlogK、可用排序如快排 N l o g N NlogN NlogN、还可以用快速选择算法即上述题4讲解的原理。 这里主要演示快速选择算法。 2、题解 以升序为例 最后我们返回时前K个元素区间虽然没有完全有序但已经满足了找出题目最小的K个数的要求。
class Solution {
public:void qsort(vectorint arr, int left, int right, int k){if(left right) return;int n right - left 1;int index rand() % n left;int key arr[index];//三指针排序: [left,right]排升序int L left - 1 , R right 1, i left;while(i R){if(arr[i] key) swap(arr[L], arr[i]);else if(arr[i] key) i;else swap(arr[--R], arr[i]);}//对左右区间:[left, L] [L1, R-1] [R,right]int a L - left 1;int b R-1 - (L1) 1;int c right - R 1;if(a k) qsort(arr, left, L, k);else if(a b k) return;else qsort(arr, R, right, k-a-b);}vectorint smallestK(vectorint arr, int k) {srand(time(nullptr));qsort(arr,0,arr.size()-1,k);return {arr.begin(),arr.begin()k};}
};6、归并排序medium 题源链接 6.1、题解复习快排二路归并 1、思路分析 在上述我们用快排解过此题这里我们使用归并排序来解决。PS归并排序相关复习见博文常见排序。 这里主要是指二路归并。 总体思想不变细节实现看个人写法 1、分割 将待排序的数组从中间分割成两个子数组直到子数组的大小为1即每个子数组只包含一个元素自然是有序的。 2、递归排序 递归地对子数组进行归并排序「左半部分排序」 「右半部分排序」。 3、合并 将两个已排序的子数组合并成一个有序的大数组。通常借助一个辅助数组可以是每次归并时创建临时变量也可以用全局变量或者在堆区开辟 2、题解
class Solution {
public:vectorint temp;void MergeSort(vectorint nums, int left, int right){if(left right) return;//这里使用二路归并选择中间点将区间划分为两段[left,mid][mid1,right]int mid ( right left ) / 2;//题中给出数据不大也可以使用防越界版本的求中间值//先对左右区间排序MergeSort(nums,left,mid);MergeSort(nums,mid1,right);//再合并两个有序数组(来到此处意味着当前左右两段区间各自有序)int cur1 left; int cur2 mid1;int i 0;while(cur1 mid cur2 right)temp[i] nums[cur1] nums[cur2] ? nums[cur1] : nums[cur2];//处理剩余区间while(cur1 mid) temp[i] nums[cur1];while(cur2 right) temp[i] nums[cur2];//将排序好的元素重新返回原数组中(可借助memcpy等函数)for(int j left; j right; j){nums[j] temp[j - left];}}vectorint sortArray(vectorint nums) {temp.resize(nums.size());//归并需要借助一个辅助数组这里可以每次归并时定义也可以直接搞一个全局变量或者堆上申请MergeSort(nums,0,nums.size()-1);return nums;}
};题外话 理论上也可以实现k路归并排序k-way merge sort其中k是大于1的整数。在k路归并排序中待排序的数组被分割成k个更小的子数组而不是仅仅两个。然后这k个子数组被分别排序并最终合并成一个完整的有序数组。 k路归并排序在某些特定场景下可能具有优势比如当待排序的数据分布在多个不连续的内存区域时或者当使用并行计算资源时。然而实现k路归并排序通常比实现二路归并排序更为复杂并且不一定总是带来性能上的提升。因此在实际应用中二路归并排序更为常见和流行。
7、数组中的逆序对hard 题源链接 7.1、题解 1、思路分析 直接解法 双层循环暴力枚举看在难度hard的份上大概率超时。 问题一为什么可以使用归并排序 1、题目要求找出数组中所有逆序对既如此将数组一分为二先找出左区间中的逆序对再找出右区间的逆序对最后选出一左一右在两区间的逆序对。效果与从左到右/从右到左线性遍历查找等同。 2、对此进行优化。在找出左区间中的逆序对后我们对其排个序同理在找出右区间的逆序对后也对其排序。此时尽管左右两区间内部元素顺序发生改变但对于在两区间中分别选取元素组成一左一右的逆序对并无影响。 3、回顾上述历程这不就和归并的思想一样吗当然在选取出一左一右的逆序对后我们要对当前整体区间也进行排序。
归并排序的过程
• 先排序左数组
• 再排序右数组
• 左数组和右数组合⼆为⼀。逆序对中两个元素
• 全部从左数组中选择逆序对
• 全部从右数组中选择逆序对
• ⼀个选左数组另⼀个选右数组组成逆序对问题二如何使用归并排序及为什么这里使用归并会提高效率(单调性) 除了这里举例的两种升序固定右值找左侧降序固定左值找右侧如何选取与组合看个人风格。 2、题解 升序写法如下
class Solution {
public:int tmp[50005]{0};int mergesort(vectorint record, int left, int right){if(left right) return 0;//取中数分区间[left, mid] [mid1, right]int mid (leftright) / 2;int sum 0;//用于统计//左区间找逆序对排序、右区间找逆序对排序sum mergesort(record,left,mid) mergesort(record,mid1,right);//一左一右找逆序对排序int cur1 left, cur2 mid 1;int i 0;while(cur1 mid cur2 right)//排升序,找左数比右数大{if(record[cur1] record[cur2])tmp[i] record[cur1];else//record[cur1] record[cur2]{sum mid - cur1 1;tmp[i] record[cur2];}}//排序处理剩余元素while(cur1 mid) tmp[i] record[cur1];while(cur2 right) tmp[i] record[cur2];//将有序数列返回原数列中for(int j left; j right; j)record[j]tmp[j-left];//返回return sum;}int reversePairs(vectorint record) {return mergesort(record,0,record.size()-1);}
};降序写法总体不变只需稍加改动即可 while(cur1 mid cur2 right)//排降序,找左数比右数大{if(record[cur1] record[cur2])tmp[i] record[cur2];else//record[cur1] record[cur2]{sum right - cur2 1;tmp[i] record[cur1];}}8、计算右侧小于当前元素的个数hard 题源链接 8.1、题解 1、思路分析 有了上一题的铺垫这一道题的解法与之类似但是这一道题要求的不是求总的个数而是要返回一个数组记录每一个元素的右边有多少个元素比自己小。 这里存在一个问题在归并排序的过程中元素的下标是会跟着变化的。 当前我们查找出的顺序与需要返回的顺序不一定完全匹配。 因此为了确保返回时数组输出的元素顺序我们需要一个额外数组 index将数组元素和对应的下标绑定在一起归并也就是在归并nums中元素的时候顺势将其下标index也转移到对应的位置上。意味着辅助数组也需要两个分别用于排序归并后的nums、index。 2、题解 这是vectorint index、vectorint count使用全局变量的版本。
class Solution {
public:int tmp_n[100005];//辅助数组1归并时用于排序numsint tmp_i[100005];//辅助数组2归并时用于排序indexvectorint index;//记录元素对应下标vectorint count;//用于返回输出结果void mergesort(vectorint nums, int left, int right){if(leftright) return;//求中值划分区间[left,mid] [mid1,right]int mid (left right) /2;//先对左右区间进行找数归并排序mergesort(nums, left, mid);mergesort(nums,mid1, right);//再对当前整段区间进行找数排序int cur1 left, cur2 mid1;int i 0;while(cur1mid cur2 right){if(nums[cur1] nums[cur2]){tmp_n[i] nums[cur2];tmp_i[i] index[cur2];//注意这里一次处理两个数组}else//nums[cur1] nums[cur2]{count[index[cur1]] right - cur2 1;tmp_n[i] nums[cur1];tmp_i[i] index[cur1];}}//处理剩余区间while(cur1 mid){tmp_n[i]nums[cur1];tmp_i[i]index[cur1];}while(cur2 right){tmp_n[i]nums[cur2];tmp_i[i]index[cur2];}//将获取到的有序数据写回原数组中for(int j left; j right; j){nums[j]tmp_n[j-left];index[j]tmp_i[j-left];}}vectorint countSmaller(vectorint nums) {int n nums.size();index.resize(n);//重新扩容count.resize(n);for(int i 0; i n; i)//初始化下标{index[i] i;}mergesort(nums, 0, n-1);return count;}
};如果不使用全局变量也可如下但需要传参时多增几个参数。总之写法不一。
class Solution {
public:int tmp_n[100005];int tmp_i[100005];void mergesort(vectorint nums, int left, int right, vectorint index, vectorint count){if(left right) return;//[left,mid] [mid1,right]int mid (left right) /2;//左右区间mergesort(nums, left, mid, index,count);mergesort(nums,mid1, right, index,count);//当前整个区间int cur1 left, cur2 mid1;int i 0;while(cur1mid cur2 right){if(nums[cur1] nums[cur2]){tmp_n[i] nums[cur2];tmp_i[i] index[cur2];}else//nums[cur1] nums[cur2]{count[index[cur1]] right - cur2 1;tmp_n[i] nums[cur1];tmp_i[i] index[cur1];}}//处理剩余区间while(cur1 mid){tmp_n[i]nums[cur1];tmp_i[i]index[cur1];}while(cur2 right){tmp_n[i]nums[cur2];tmp_i[i]index[cur2];}//写回原数组中for(int j left; j right; j){nums[j]tmp_n[j-left];index[j]tmp_i[j-left];}}vectorint countSmaller(vectorint nums) {int n nums.size();vectorint index(n);vectorint count(n);for(int i 0; i n; i){index[i] i;}mergesort(nums, 0, n-1, index, count);return count;}
};关于count[index[cur1]] right - cur2 1; 为什么要用而不能使用 要知道归并的过程元素位置是变化的。 使用 是因为我们需要累计 nums[cur1] 右侧小于它的元素数量。在归并排序的合并过程中cur1 会遍历左子数组的所有元素每次遇到一个比右子数组当前元素大的左子数组元素时我们都需要将右子数组中剩余的元素数量即 right - cur2 1累加到对应的 count 中。因此这是一个累加操作每次都需要将新的数量加到之前累计的数量上。 如果使用 而不是 那么每次只会将 right - cur2 1 赋值给 count[index[cur1]]而不会保留之前累计的数量。这会导致 count 数组中每个位置只存储了最后一次计算得到的数量而不是所有累计的数量从而得到错误的结果。 9、翻转对hard 题源链接 9.1、题解 1、思路分析 翻转对和逆序对的定义大同小异逆序对是前面的数要大于后面的数。而翻转对是前面的一个数要大于后面某个数的两倍。因此我们依旧可以用归并排序的思想来解决这个问题。 而与上个问题不同的是上一道题我们可以一边合并一遍计算小于当前元素右侧元素但是这道题要求的是左边元素大于右边元素的两倍若直接合并的话是无法快速计算出翻转对的数量的。 因此在归并排序之前我们可以借助左右区间已经排序好的单调性先完成对翻转对的统计。由于两个指针都是不回退的的扫描到数组的结尾因此两个有序序列求出翻转对的时间复杂度是 O ( N ) O(N) O(N)。 2、题解 以升序为例
class Solution {
public:int tmp[50005] {0};int mergesort(vectorint nums, int left, int right) {if (left right)return 0;//[left,mid] [mid1, right]int mid (left right) / 2;int sum 0;sum mergesort(nums, left, mid) mergesort(nums, mid 1, right);// 统计(单调性为升序)int cur1 left, cur2 mid 1;while(cur1 mid cur2 right){if(nums[cur1]/2.0 nums[cur2]){sum mid - cur1 1;cur2;}else cur1;}// while (cur2 right) // 统计部分其它写法升序的情况// {// while (cur1 mid nums[cur2] nums[cur1] / 2.0)// cur1;// if (cur1 mid)// break;// sum mid - cur1 1;// cur2;// }// 排序升序版,[left, mid][mid1, right]cur1 left, cur2 mid 1;int i left;while (cur1 mid cur2 right) {if (nums[cur1] nums[cur2])tmp[i] nums[cur2];elsetmp[i] nums[cur1];}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];}return sum;}int reversePairs(vectorint nums) {return mergesort(nums, 0, nums.size()-1);}
};以降序为例
class Solution {
public:int tmp[50005] {0};int mergesort(vectorint nums, int left, int right) {if (left right)return 0;//[left,mid] [mid1, right]int mid (left right) / 2;int sum 0;sum mergesort(nums, left, mid) mergesort(nums, mid 1, right);// 统计(单调性为降序)int cur1 left, cur2 mid 1;while (cur1 mid cur2 right) {if (nums[cur1] / 2.0 nums[cur2]) {sum right - cur2 1;cur1;} elsecur2;}// while (cur1 mid) // 统计部分其它写法降序的情况// {// while (cur2 right nums[cur2] nums[cur1] / 2.0)// cur2;// if (cur2 right)// break;// ret right - cur2 1;// cur1;// }// 排序降序版,[left, mid][mid1, right]cur1 left, cur2 mid 1;int i left;while (cur1 mid cur2 right) {tmp[i] nums[cur1] nums[cur2] ? nums[cur1] : 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];}return sum;}int reversePairs(vectorint nums) {return mergesort(nums, 0, nums.size() - 1);}
};Fin、共勉。
