58招聘运营网站怎么做项目申报

58招聘运营网站怎么做,项目申报,引流推广话术文案,信誉好的赣州网站建设分治#xff1a;将一个大问题转化成若干个相同或相似的子问题#xff0c;直到划分的子问题能够快速解决。排序中的快速排序和归并排序就运用了分治的思想。 算法题目 题目1#xff1a;75. 颜色分类 - 力扣#xff08;LeetCode#xff09; 题目分析 给定一个包含红色、白色…分治将一个大问题转化成若干个相同或相似的子问题直到划分的子问题能够快速解决。排序中的快速排序和归并排序就运用了分治的思想。算法题目题目175. 颜色分类 - 力扣LeetCode题目分析给定一个包含红色、白色和蓝色、共n个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数0、1和2分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。题目示例示例 1输入nums [2,0,2,1,1,0]输出[0,0,1,1,2,2]示例 2输入nums [2,0,1]输出[0,1,2]算法原理在双指针算法 —— 《移动零》那道题目中使用双指针将 nums 数组划分成2个区域。这道题需要使用三个指针将 nums 数组划分成3个区域这是题目要求的。定义三个指针left,right,cur。left 标记0区域的最右侧right 标记2区域的最左侧。cur 遍历整个 nums 数组如此就将 nums 数组划分成了3块区域。然而在遍历的过程中3个指针会将 nums 数组划分成4部分left 的初始值为-1cur 的初始值为0right 的初始值为n循环条件为 cur right。上述 4 个区域的特点[0,left]区域元素全都是0[left1,cur-1]元素全都是1[cur, right-1]待处理元素[right, n-1]元素全都是2接下来仅需处理 cur 所指向位置的情况若 cur 指向的元素等于0leftleft指向的元素与cur指向的元素交换cur若 cur 指向的元素等于1cur若 cur 指向的元素等于2right 指向的元素与 cur 指向的元素交换right--cur 不移动。为什么 cur 不移动呢因为 right 交换过来的元素是未处理的不确定它是否等于2left 的初始值为-1cur 的初始值为0right 的初始值为 n循环条件为 cur right。使用具体示例来演示算法过程代码实现class Solution { public: void sortColors(vectorint nums) { int left -1, cur 0, right nums.size(); while(cur right) { // nums[cur] 0,left,swap(nums[left], nums[cur]),cur if(nums[cur] 0) { swap(nums[left], nums[cur]); } // nums[cur] 2,right--,swap(nums[right], nums[cur]) else if(nums[cur] 2) { swap(nums[--right], nums[cur]); } // nums[cur] 1,cur else { cur; } } } };题目2912. 排序数组 - 力扣LeetCode题目分析给你一个整数数组nums请你将该数组升序排列。你必须在不使用任何内置函数的情况下解决问题时间复杂度为O(nlog(n))并且空间复杂度尽可能小。题目示例示例 1输入nums [5,2,3,1]输出[1,2,3,5]解释数组排序后某些数字的位置没有改变例如2 和 3而其他数字的位置发生了改变例如1 和 5。示例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]解释请注意nums 的值不一定唯一。算法原理可以使用快速排序也可以选择归并排序这里我使用快速排序来解决问题后面会使用归并排序来解决。快速排序需要找到一个基准值 keykey 左边的元素都是小于等于 key右边的元素都是大于 key。之后再将 key 的左区域看成一部分key 的右区域看成一部分继续找基准值继续划分区域。但是如果 nums 数组中的相同元素很多或者说全是相同的元素那么 key 值的确定时间复杂度是很高的。因此使用双指针来确定 key 值不是最优的解法使用三指针来确定 key 值将 nums 数组分成3块。中间区域一定在它应当在的位置所以仅需考虑小于 key 和大于 key 的区域继续划分找key。算法流程定义三个指针leftrightcurleft 初始值为0right 初始值为n-1若 nums[cur] keyleftswap(nums[left], nums[cur])cur若 nums[cur] keycur若 nums[cur] keyright--swap(nums[right], nums[cur])操作执行完毕之后就将 nums 划分成 3 部分了接着再递归排左右两区域key 的选取key的初始值为随机值key rand() % (right – left 1) left生成的随机数模上区间的长度之后得到的数都是小于 [left, right] 区间的数再加上 left进一步增加了随机性代码实现class Solution { public: vectorint sortArray(vectorint nums) { // 生成随机数种子 srand(time(NULL)); // 快速排序 qsort(0, nums.size() - 1, nums); return nums; } // 快速排序 void qsort(int begin, int end, vectorint nums) { // 递归出口 if(begin end) { return; } // 获得基准值key int key nums[rand() % (end - begin 1) begin]; // 定义三个指针 int left begin - 1, cur begin, right end 1; // 划分 while(cur right) { if(nums[cur] key) { swap(nums[left], nums[cur]); } else if(nums[cur] key) { swap(nums[--right], nums[cur]); } else { cur; } } // 排序 [begin, left],[left 1 right - 1],[right, end] qsort(begin, left, nums); // 左区域 qsort(right, end, nums); // 右区域 } };题目3215. 数组中的第K个最大元素 - 力扣LeetCode题目分析给定整数数组nums和整数k请返回数组中第k个最大的元素。请注意你需要找的是数组排序后的第k个最大的元素而不是第k个不同的元素。你必须设计并实现时间复杂度为O(n)的算法解决此问题。top K 问题找第k大找第k小找前k大找前k小。涉及top K 问题解决方法右两种堆排序和快速选择。堆排序解决找第k大找第k小的问题快速选择解决找前k大找前k小的问题。堆排序的时间复杂度为O(NlogN)快速选择的时间复杂度为O(N)。根据具体题目的要求来解决问题。本题是找第K大的元素应当使用堆排序但是题目要求时间复杂度为 O(N)因此需要使用快速选择来解决问题。题目示例示例 1:输入:[3,2,1,5,6,4],k 2输出:5示例 2:输入:[3,2,3,1,2,4,5,5,6],k 4输出:4算法原理需要注意 nums 数组是升序的可以使用三指针降 nums 分成3部分。题目要求找第K大的元素它可能在小于 key等于 key大于 key 的区域。如果能够确定第K大的元素落在大于 key 的区域内那么其它两个区域就不需要考虑了。接下来思考如何确定第K大的元素位于哪个区间设小于 key 区间中元素的个数为 a等于 key 区间中元素的个数为b大于 key 区间中元素的个数为c。如果目标值在大于 key 区域内那么区间中的元素个数 c 要大于等于K。要找的目标值是 nums 数组中第K大的元素而大于 key 区间的元素都是 nums 数组中的较大的元素。若区间的元素个数c大于等于K那么K一定在大于key区域内。然后仅需在大于 key 区间中寻找即可大于 key 区间的边界是什么根据以上两题的经验大于 key 区间为[right, end]。接下来再去该区域寻找第K大的元素。若 c 小于K那么第K大的元素一定落在小于等于 key 区间内。若 bc 大于等于K那么第K大的元素一定在等于 key 区间内此时直接返回 key。若 bc 小于K那么第K大的元素一定在小于 key 区间内。此时就不是在找第K大的元素了因为大于等于 key 区间内的元素都被排除了要知道它们都是nums中最大的几个数将这些数都给排除了那么说明在小于 key 区间中要找的元素就是第 K – b – c 大的元素。代码实现class Solution { public: int findKthLargest(vectorint nums, int k) { // 生成随机数种子 srand(time(NULL)); return qsort(0, nums.size() - 1, k, nums);; } // 排序 int qsort(int begin, int end, int k, vectorint nums) { // 当区间只有一个元素直接返回这个元素 if(begin end) { return nums[begin]; } // 为什么不考虑 begin end,即区间不存在的情况 // 接下来的判断条件会保证只要进入了qsort函数区间一定存在 // 随机数确定基准值 int key nums[rand() % (end - begin 1) begin]; // 三个指针 int left begin - 1, cur begin, right end 1; // 划分 while(cur right) { if(nums[cur] key) { swap(nums[left], nums[cur]); } else if(nums[cur] key) { swap(nums[--right], nums[cur]); } else { cur; } } // [begin, left],[left1, right-1],[right, end] // 统计区间中的元素个数 int numleft left - begin 1; int nummid (right-1) - (left1) 1; int numright end - right 1; // 落在[right, end]区间中 if(numright k) { //在[right, end]中找第K大的元素 return qsort(right, end, k, nums); } // 落在[left1, right-1]区间中 else if(nummid numright k) { // 直接返回基准值 return key; } // 落在[begin, left]区间中 else { // 在[begin, left]中找第K - nummid - numright 大的元素 return qsort(begin, left, k-nummid-numright, nums); } } };题目4LCR 159. 库存管理 III - 力扣LeetCode题目分析仓库管理员以数组stock形式记录商品库存表其中stock[i]表示对应商品库存余量。请返回库存余量最少的cnt个商品余量返回顺序不限。题目翻译找数组中前cnt(K)个小的元素题目示例示例 1输入stock [2,5,7,4], cnt 1输出[2]示例 2输入stock [0,2,3,6], cnt 2输出[0,2] 或 [2,0]算法原理解法1排序排完升序之后再将前 k 个元素返回。解法2建堆找前 K 个最小的元素是创建大小为K的大根堆最后堆中剩下的元素就是前 K 个最小的元素。解法3快速选择算法思路与前面几道使用快速选择算法的思路一致。排完序之后再将前k个最小的数返回。假设 [begin, left][left1, right-1][right, end] 区间的元素个数分别为a,b,c。若 ak则说明前 k 个最小的元素在 [begin, left ] 区间在 [begin, left] 区间中找。若不满足ak满足abk则说明第 k 小的元素在 [left1, right-1] 区间中因为 [ left1, right-1] 区间中元素都是相等的那么以找到的第K小的下标位置为分割点左边的元素就是前 k 个最小的元素题目不要求返回有序因此可以直接返回。若不满足 akabk满足 abck则说明第k小的元素在[right, end]区间内在[begin, right-1]区间中的元素都是数组nums中的较小元素它们都不满足说明k很大那么在[right, end]区间找的也不是前k小的元素而是前个 k-a-b 最小的元素。代码实现class Solution { public: vectorint inventoryManagement(vectorint stock, int cnt) { // 生成随机数种子 srand(time(NULL)); // qsort不是将数组排序而是将前k小的元素移动到前面 qsort(0, stock.size()-1, cnt, stock); // 如此仅需取前k个数组作为返回值即可 return {stock.begin(), stock.begin() cnt}; } void qsort(int begin, int end, int k, vectorint nums) { // 递归结束的条件 if(begin end) { return; } // 随机生成基准值 int key nums[rand() % (end - begin 1) begin]; // 定义三个指针 int left begin - 1, cur begin, right end 1; // 划分 while(cur right) { if(nums[cur] key) { swap(nums[left], nums[cur]); } else if(nums[cur] key) { swap(nums[--right], nums[cur]); } else { cur; } } // 统计区间中元素的个数 // [begin, left],[left1, right-1],[right, end] int numleft left - begin 1; int nummid (right-1) - (left1) 1; // 若numleft大于k则说明前k个最小的元素在[begin, left]区间 if(numleft k) { qsort(begin, left, k, nums); } // 在[begin, left]区间中找 // 若不满足前面的条件满足numleftnummid大于k // 则说明第k小的元素在[left1, right-1]区间里 // 那么它的左边部分就是前k个最小的元素 else if(numleft nummid k) { return; } // 若不满足前面的条件 // 则说明第k小的元素在[right, end]区间中 // 在[right, end]区间中找的不是第K小的元素而是第k-numleft-nummid小的元素 else { qsort(right, end, k-numleft-nummid, nums); } } };题目5912. 排序数组 - 力扣LeetCode题目分析给你一个整数数组nums请你将该数组升序排列。你必须在不使用任何内置函数的情况下解决问题时间复杂度为O(nlog(n))并且空间复杂度尽可能小。题目示例示例 1输入nums [5,2,3,1]输出[1,2,3,5]解释数组排序后某些数字的位置没有改变例如2 和 3而其他数字的位置发生了改变例如1 和 5。示例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]解释请注意nums 的值不一定唯一。算法原理之前是使用快速排序的思想来解决这道问题接下来使用归并排序的思想来解决这个问题。寻找一个中间点 mid将 nums 分成左右两个部分在排序左区域和右区域时使用相同的步骤。当最终分成的区域只有一个元素的时候才开始向上返回合并两个有序数组。对比快速排序和选择排序代码实现class Solution { public: vectorint sortArray(vectorint nums) { // 归并排序 MergeSort(0, nums.size() - 1, nums); return nums; } void MergeSort(int left, int right, vectorint nums) { // 递归的终止条件 if(left right) { return; } // 1. 选择中间点 // 中间值mid int mid left (right - left) / 2; // 2. 划分左右两个区域 // 划分 [left, mid],[mid1, right] MergeSort(left, mid, nums); MergeSort(mid1, right, nums); // 3. 合并两个数组 // 确定两个数组的边界 int begin left, end mid; // 遍历第一个数组 int front mid 1, back right; // 遍历第二个数组 // 辅助数组 vectorint ret(right - left 1); int i 0; // 辅助数组的下标 while(begin end front back) { if(nums[begin] nums[front]) { ret[i] nums[begin]; } else { ret[i] nums[front]; } } // 处理未遍历完的数组 while(begin end) { ret[i] nums[begin]; } while(front back) { ret[i] nums[front]; } // 4. 还原 for(int i left; i right; i) { nums[i] ret[i - left]; } } };在函数中创建一个数组用于辅助数组的合并但是每次递归都需要创建一个辅助数组开销有点大。看它的执行用时分布如果将辅助数组 ret 定义成全局的在调用MergeSort函数之前就预先开辟好空间算法的执行用时分布会大大减小class Solution { public: // 辅助数组定义成全局的 vectorint ret; vectorint sortArray(vectorint nums) { // 预开辟空间,使用resize函数 ret.resize(nums.size()); // 归并排序 MergeSort(0, nums.size() - 1, nums); return nums; } void MergeSort(int left, int right, vectorint nums) { // 递归的终止条件 if(left right) { return; } // 1. 选择中间点 // 中间值mid int mid left (right - left) / 2; // 2. 划分左右两个区域 // 划分 [left, mid],[mid1, right] MergeSort(left, mid, nums); MergeSort(mid1, right, nums); // 3. 合并两个数组 // 确定两个数组的边界 int begin left, end mid; // 遍历第一个数组 int front mid 1, back right; // 遍历第二个数组 int i 0; // 辅助数组的下标 while(begin end front back) { if(nums[begin] nums[front]) { ret[i] nums[begin]; } else { ret[i] nums[front]; } } // 处理未遍历完的数组 while(begin end) { ret[i] nums[begin]; } while(front back) { ret[i] nums[front]; } // 4. 还原 for(int i left; i right; i) { nums[i] ret[i - left]; } } };执行用时分布题目6LCR 170. 交易逆序对的总数 - 力扣LeetCode题目分析在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录record返回其中存在的「交易逆序对」总数。题目示例示例 1输入record [9, 7, 5, 4, 6]输出8解释交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。算法原理解法1暴力枚举将所有的二元组枚举出来再判断是否是逆序对。两层 for 循环。解法2使用归并排序的思想在求整个数组的逆序对时是否可以寻找一个中间点将 nums 数组分成两部分。先求左部分有多少个逆序对再求右部分有多少个逆序对然后在左区间中选择一个元素在右区间中选择一个元素若共组成了c个逆序对假设左部分有a个逆序对右部分有b个逆序对那么最终 nums 中逆序对的数量为a b c。它的本质仍然是暴力枚举。使用例子来演示record [9, 7, 5, 4, 6]在上述策略的基础上进行扩展左半部分的逆序对查找完毕之后左半部分进行排序右半部分的逆序对查找完毕之后右半部分进行排序最后再从左区域和右区域找逆序对。为什么需要排序之后再左右找因为左区间的元素都是在右区间元素的前面在左区间中选取一个元素再右区间中找比它小的元素即可。在左右区间寻找完毕之后需要进行排序。从中间选取一个数将数组分成左右两部分左右两区间在从中间选取一个数将区间分成左右两部分直到区间不能再分割这不就是归并排序的思想吗为什么要使用查找完毕之后还要将序列排好序思想1在[mid1, right]区间找到一个数之前有多少个数比nums[cur2]大数组是升序的[left, cur1] 区间的元素一定是小于 cur1 所指向的元素[right,cur2] 区间的元素一定是小于 cur2 所指向的元素。这样在一左一右找逆序对时仅需在 [left,mid] 左区间找到有几个数大于nums[cur2]。因此需要对cur1和cur2指向的元素进行比较nums[cur1] nums[cur2]cur1nums[cur1] nums[cur2]由于数组是升序的即 [left, mid] 左区间也是升序cur1 指向的元素都大于 cur2那么 cur1 后面的元素都大于 cur2。让返回值 ret 加上 [cur1, mid] 区间的元素个数即 ret mid – cur1 1一次性就能统计一堆逆序对最后 cur2 继续向后移动。cur1 和 cur2 的移动恰好与归并排序中指针的移动相似因此在合并数组的时候就可以统计逆序对。如果数组是降序的呢在 [mid1, right] 区间找到一个数之前有多少个数比 nums[cur2] 大[left, cur1]区间的元素一定是大于nums[cur1][mid1, cur2]区间的元素一定是大于nums[cur2]。在一左一右找逆序对时仅需在 [left,mid] 左区间找到有几个数大于 nums[cur2]。如果 nums[cur1] nums[cur2]需要统计 [left, cur1] 区间中有多少个元素ret cur1 – left 1然后 cur1如果 nums[cur1] 仍然大于 nums[cur2]统计 [left, cur1] 区间中有多少个元素ret cur1 – left 1这样会多加。难道降序没有用了吗当然不是只是它不适合用在这。思想2在 [left, mid] 区间找到一个数之后有多少个数比 nums[cur1] 小若数组是升序的[left, cur1] 区间的元素都是小于 nums[cur1][mid1, cur2] 区间的元素都是小于 nums[cur2]。在一左一右找逆序对时仅需在 [mid1,right] 右区间找到有几个数小于 nums[cur1]。若 nums[cur1] nums[cur2]由于数组的是升序的cur2 前面的数都是小于它的连 nums[cur2]都小于 nums[cur1] 了cur2 前面的元素肯定也小于 nums[cur1]因此统计 [mid1, cur2] 区间的元素个数即 ret cur2 – (mid1) 1。接着 cur1若 nums[cur1] 仍然大于 nums[cur2]统计 [mid1, cur2] 区间的元素个数这样会多加。若数组是降序[left, cur1] 区间的元素都是小于 nums[cur1][mid1, cur2] 区间的元素都是小于 nums[cur2]。在一左一右找逆序对时仅需在 [mid1,right] 右区间找到有几个数小于 nums[cur1]。当 nums[cur1] nums[cur2]数组的是降序说明 cur2 后面的元素都小于nums[cur2]因此可以统计区间[right, cur2]的元素个数即ret right – cur2 1。然后 cur1若 nums[cur1] 仍然大于 nums[cur2]再次统计 [right, cur2] 的元素个数不会多加因为 [cur2, right] 区间对应的 cur1是不一样的。若 nums[cur1] nums[cur2]cur2。代码实现升序class Solution { public: // 定义全局变量的辅助数组 tmp vectorint tmp; int reversePairs(vectorint record) { // records元素的个数 int n record.size(); // 处理 tmp 辅助数组 tmp.resize(n); return MergeSort(0, n - 1, record); } int MergeSort(int left, int right, vectorint nums) { // 递归终止的条件 if(left right) { return 0; } // 返回值 int ret 0; // 找中间点 int mid left (right- left) / 2; // 将nums数组划分成两部分 [left, mid],[mid1, right] // 统计左区间中逆序对的个数排序左区间 ret MergeSort(left, mid, nums); // 统计右区间中逆序对的个数排序右区间 ret MergeSort(mid1, right, nums); // 一左一右 // 确定左右区间的指针 int begin left, end mid; int front mid 1, back right; int i 0; //辅助数组的下标索引 while(begin end front back) { // 升序 if(nums[begin] nums[front]) { ret (end - begin 1); tmp[i] nums[front]; // 小的加入 } else { tmp[i] nums[begin]; } } // 处理剩下未遍历到的 while(begin end) { tmp[i] nums[begin]; } while(front back) { tmp[i] nums[front]; } // 还原 for(int j left; j right; j) { nums[j] tmp[j - left]; } return ret; } };代码实现降序class Solution { public: // 定义全局变量的辅助数组 tmp vectorint tmp; int reversePairs(vectorint record) { // records元素的个数 int n record.size(); // 处理 tmp 辅助数组 tmp.resize(n); return MergeSort(0, n - 1, record); } int MergeSort(int left, int right, vectorint nums) { // 递归终止的条件 if(left right) { return 0; } // 返回值 int ret 0; // 找中间点 int mid left (right- left) / 2; // 将nums数组划分成两部分 [left, mid],[mid1, right] // 统计左区间中逆序对的个数排序左区间 ret MergeSort(left, mid, nums); // 统计右区间中逆序对的个数排序右区间 ret MergeSort(mid1, right, nums); // 一左一右 // 确定左右区间的指针 int begin left, end mid; int front mid 1, back right; int i 0; //辅助数组的下标索引 while(begin end front back) { // 降序 if(nums[begin] nums[front]) { ret (back - front 1); tmp[i] nums[begin]; // 大的加入 } else { tmp[i] nums[front]; } } // 处理剩下未遍历到的 while(begin end) { tmp[i] nums[begin]; } while(front back) { tmp[i] nums[front]; } // 还原 for(int j left; j right; j) { nums[j] tmp[j - left]; } return ret; } };题目7315. 计算右侧小于当前元素的个数 - 力扣LeetCode题目分析给你一个整数数组nums按要求返回一个新数组counts。数组counts有该性质counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。这和上一道题求逆序对的数量十分相似只不过这里是求每一个数与右边的数组成的逆序对的数量。题目示例示例 1输入nums [5,2,6,1]输出[2,1,1,0]解释5 的右侧有2个更小的元素 (2 和 1) 2 的右侧仅有1个更小的元素 (1) 6 的右侧有1个更小的元素 (1) 1 的右侧有0个更小的元素示例 2输入nums [-1]输出[0]示例 3输入nums [-1,-1]输出[0,0]算法原理解法归并排序本题求的是当前元素比我小的元素也就是使用上一题的思想2 ——数组降序。上一题是将 nums 分成两部分先统计左区域中逆序对的个数再统计右区域中逆序对的个数最后统计一左一右区域的逆序对个数。而这道题仅需计算一左一右的逆序对个数。需要注意数组是降序因此 [left, cur1] 区间的元素都是大于 nums[cur1][mid1, cur2] 区间的元素都是大于 nums[cur2]找当前元素比我小的元素即在 [mid1, right] 右区间找比 nums[cur1] 小的元素。若 nums[cur1] nums[cur2]由于数组是降序那么 cur2 后面的元素都是小于它的连nums[cur2] 都小于 nums[cur1] 了那么 cur2 后面的元素也小于。统计 [cur2, right] 区间的元素个数需要注意的是要将结果存放到数组 count 中并且下标的位置要相对应即假设元素的下标为index则 count[index] right – cur2 1且 cur1。若nums[cur1] nums[cur2]cur2。需要注意一定是 为什么接下来解决一个问题如何找到正在统计逆序对的元素的下标cur1 不就是元素的下标需要注意的是数组已经排好序了下标已经乱了要找到 nums 数组中元素的原始下标。这里不能使用hash 表因为我们的目的是将元素与下标向绑定如果 nums 中存在相同的元素呢因此不能使用 hash 表。使用 pair将元素与下标绑定在一起。代码实现class Solution { public: // 返回值 vectorint count; // 辅助数组 vectorpairint, int tmp; vectorint countSmaller(vectorint nums) { // nums中元素的个数 int n nums.size(); // 处理count count.resize(n); // 一定要处理tmp辅助数组 tmp.resize(n); // 将nums中的元素与其下标一起绑定 // int, int - nums[i], i // first-nums[i] second-i vectorpairint, int index; for(int i 0; i n; i) { index.push_back({nums[i], i}); } // 解决问题 MergeSort(0, n - 1, index); return count; } void MergeSort(int left, int right, vectorpairint, int index) { // 递归的结束条件 if(left right) { return; } // 取中间点 int mid left (right - left) / 2; // 将数组分成两部分 [left, mid],[mid1, right] —— 排序 MergeSort(left, mid, index); MergeSort(mid1, right, index); // 处理一左一右的情况 int begin left, end mid; // 左区域 int front mid 1, back right; // 右区域 int i 0; // 辅助数组的下标 // 需要注意数组是降序的 while(begin end front back) { // first 进行比较 if(index[begin].first index[front].first) { // 一定要注意是 count[index[begin].second] back - front 1; tmp[i] index[begin]; } else { tmp[i] index[front]; } } // 未处理的元素 while(begin end) { tmp[i] index[begin]; } while(front back) { tmp[i] index[front]; } // 还原 for(int j left; j right; j) { index[j] tmp[j - left]; } } };题目8493. 翻转对 - 力扣LeetCode题目分析给定一个数组nums如果i j且nums[i] 2*nums[j]我们就将(i, j)称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。题目示例示例 1:输入: [1,3,2,3,1]输出: 2示例 2:输入: [2,4,3,5,1]输出: 3注意:给定数组的长度不会超过50000。输入数组中的所有数字都在32位整数的表示范围内。示例分析例nums [1,3,2,3,1]示例nums [2,4,3,5,1]算法原理这道题的解法与求逆序对的解法一致要求整个数组翻转对的个数可以变成求左右区间和一左一右的翻转对的个数。统计 [left, mid] 区间中翻转对的个数[mid1, right] 区间翻转对的个数再统计一左一右各取一个数的翻转对的个数。但是需要注意的是在解决逆序对那道题时只需要比较 nums[i] 和 nums[j] 的大小与归并排序中比较的内容是相似的因此可以在合并的同时统计逆序对的个数。这里 nums[i] 2*nums[j]比较的内容与归并排序的并不一致因此需要在排完序之后合并两个数组之前计算翻转对个数因为要利用两个数组有序的性质。思路1计算当前元素后面有多少个元素的两倍比 nums[cur1]小 推荐降序利用数组的单调性使用同向双指针统计翻转对的个数。若 nums[cur1] 2*nums[cur2]cur2。若 nums[cur1] 2*nums[cur2]要知道数组是降序的那么 cur2 后面的元素肯定是小于 cur2 的连 2*nums[cur2 ]都小于 nums[cur1] 了更何况 cur2 后面的元素统计出 [cur2, right] 区间中元素的个数ret (right – cur2 1)最后 cur1。统计后 cur2 不需要回退要知道数组是降序的在 [left, mid] 区间中nums[cur1] 就是最大的元素如果将 cur2 回退到原来的位置只会重复之前的操作连区间中最大的元素 nums[cur1] 都经历了那些操作更何况 cur1 后面的元素因此 cur2 不需要回退直接避免了重复相同的操作只需要 cur1 向后移动即可。思路2计算当前元素之前有多少个元素的一半比 nums[cur2] 大推荐升序若nums[cur1] / 2 nums[cur2]cur1。若 nums[cur1] / 2 nums[cur2]要知道数组是升序的那么 cur1 后面的元素的一半一定是大于 nums[cur2]连 nums[cur1] 的一半都大于 nums[cur2] 了更何况后面的元素统计 [cur1, mid] 区间元素的个数ret mid – cur1 1最后 cur2。统计后 cur1 不需要回退要知道数组是升序的在 [mid1, right] 区间中nums[cur2] 就是最小的元素cur2 向后移动后nums[cur2] 会变大。如果将 cur1 回退到起始位置只会经历和之前相同的操作因此 cur1 不需要回退。代码实现降序class Solution { public: // 辅助数组 vectorint tmp; int reversePairs(vectorint nums) { // nums元素个数 int n nums.size(); // 处理辅助数组tmp tmp.resize(n); return MergeSort(0, n - 1, nums); } int MergeSort(int left, int right, vectorint nums) { // 递归的终止条件 if(left right) { return 0; } // 返回值 int ret 0; // 取中间点 int mid left (right - left) / 2; // 将nums划分成两个区域 [left, mid],[mid1, right] ret MergeSort(left, mid, nums); ret MergeSort(mid 1, right, nums); // 计算翻转对的个数 int cur1 left, cur2 mid 1; while(cur1 mid cur2 right) { // 降序 // long long 类型避免2*nums[cur2]溢出 if(nums[cur1] (long long)2*nums[cur2]) { ret right - cur2 1; cur1; } else { cur2; } } // 合并两个数组 int begin left, end mid; // 左区域 int front mid1, back right; // 右区域 // 辅助数组tmp的下标 int i 0; // 合并两个数组 while(begin end front back) { if(nums[begin] nums[front]) { tmp[i] nums[begin]; } else { tmp[i] nums[front]; } } // 未处理的元素 while(begin end) { tmp[i] nums[begin]; } while(front back) { tmp[i] nums[front]; } // 还原 for(int j left; j right; j) { nums[j] tmp[j - left]; } return ret; } };代码实现升序class Solution { public: // 辅助数组 vectorint tmp; int reversePairs(vectorint nums) { // nums元素个数 int n nums.size(); // 处理辅助数组tmp tmp.resize(n); return MergeSort(0, n - 1, nums); } int MergeSort(int left, int right, vectorint nums) { // 递归的终止条件 if(left right) { return 0; } // 返回值 int ret 0; // 取中间点 int mid left (right - left) / 2; // 将nums划分成两个区域 [left, mid],[mid1, right] ret MergeSort(left, mid, nums); ret MergeSort(mid 1, right, nums); // 计算翻转对的个数 int cur1 left, cur2 mid 1; while(cur1 mid cur2 right) { // 升序 // 注意除的是 2.0 if(nums[cur1]/2.0 nums[cur2]) { ret mid - cur1 1; cur2; } else { cur1; } } // 合并两个数组 int begin left, end mid; // 左区域 int front mid1, back right; // 右区域 // 辅助数组tmp的下标 int i 0; // 合并两个数组 while(begin end front back) { if(nums[begin] nums[front]) { tmp[i] nums[front]; } else { tmp[i] nums[begin]; } } // 未处理的元素 while(begin end) { tmp[i] nums[begin]; } while(front back) { tmp[i] nums[front]; } // 还原 for(int j left; j right; j) { nums[j] tmp[j - left]; } return ret; } };知识回顾C语言排序算法的底层逻辑与性能对比_排序csdn-CSDN博客