推荐网站建设品牌,电子商务网站的开发语言,c2c的代表性电商平台,手机网站用什么做文章目录 1、排序数组2、数组中的逆序对3、计算右侧小于当前元素的个数4、翻转对 本篇前提条件是已学会归并排序 1、排序数组
912. 排序数组 排序数组也可以用归并排序来做。 vectorint tmp;//写成全局是因为如果在每一次小的排序中都创建一次#xff0c;更消耗时间和… 文章目录 1、排序数组2、数组中的逆序对3、计算右侧小于当前元素的个数4、翻转对 本篇前提条件是已学会归并排序 1、排序数组
912. 排序数组 排序数组也可以用归并排序来做。 vectorint tmp;//写成全局是因为如果在每一次小的排序中都创建一次更消耗时间和空间设置成全局的就更高效vectorint sortArray(vectorint nums) {tmp.resize(nums.size());mergeSort(nums, 0, nums.size() - 1);return nums;}//归并做法void mergeSort(vectorint nums, int left, int right){if(left right) return ;int mid (left right) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid 1, right);int cur1 left, cur2 mid 1, i 0;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 i left; i right; i){nums[i] tmp[i - left];}}2、数组中的逆序对
剑指 Offer 51. 数组中的逆序对 如果暴力枚举一定是可以解决问题的但肯定不用这个解法。选择逆序对可以先把数组分成两部分左半部分 右半部分的逆序对以及再找左半部分的数字和右半部分数字成对的数比如上面例子中7和67和4就是这种情况。左 右 一左一右就是整体的逆序对数量。当这两半部分都处理完后就扩大区间继续上述操作。这个解法也就是利用归并排序归并排序的思路就是划分到最小的区间只有1个数它一定是有序的回到上一层也就是2个数的区间让它们排好序在它右边的也是2个数的区间重复和它一样的操作这样两个区间都有序后再往上走一层来到4个数的区间4个数每一半都是有序的将整体的4个数排成有序的再往上走来到8个数的区间重复操作。
利用归并排序的思路我们在两个区间都排成升序后定义两个指针cur指向两个区间的开头然后一左一右比较大小如果cur1比cur2大那么cur1之后都比cur2大就可以一次性加上多个逆序对的个数。
下面的代码可以从最小的区间开始一个个代入来理解。从只有2个数的区间开始走到递归处分成2个只有1个数的区间那就会返回0两处递归走完来到下面的循环此时left是0right是1mid是0带入进去会发现最后的ret只会是0或者1并且这2个数也在最后排好序了返回后来到上一层也就是走左边递归的那行代码然后再走右边也是2个数也是同样的操作2个区间排好序了4个数的区间就一左一右比较大小找出逆序对排好序再走到上一层8个数的区间也是如此。
class Solution {int tmp[50010];
public:int reversePairs(vectorint nums) {return mergeSort(nums, 0, nums.size() - 1);}int mergeSort(vectorint nums, int left, int right){if(left right) return 0;int ret 0;//1. 找中间点将数组分成两部分int mid (left right) 1;// [left, mid] [mid 1, right]//2. 左边个数 排序 右边个数 排序ret mergeSort(nums, left, mid);ret mergeSort(nums, mid 1, right);//3. 一左一右的个数int cur1 left, cur2 mid 1, i 0;while(cur1 mid cur2 right)//while体内原本是归并排序的代码现在就多加一点{if(nums[cur1] nums[cur2]) tmp[i] nums[cur1];else{ret mid - cur1 1;tmp[i] nums[cur2];}}//4. 处理排序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 ret;}
};3、计算右侧小于当前元素的个数
315. 计算右侧小于当前元素的个数 此题和上一个题有相同之处也是分治也是利用归并排序这道题可以看作当前元素后面有多少比我小的而上一题则是当前元素前面有多少比我大的。仔细想一想上一题是排升序这一题排降序则更为合适。这题和上一题还有不同的地方。
cur1和cur2排成降序如果cur1 cur2cur2因为我们要找比当前元素小的如果cur1 cur2由于是降序那么cur2之后的肯定都小但这里不能加上ret我们要返回一个数组要把这个数加在当前元素的原始下标因为数组已经被我们给排序了所以要找原始下标。这里的做法就是从最一开始就除了tmp外再定义一个数组存储着原始下标因为这时候还没开始排序可以找得到然后每次原数组元素变换位置这个下标数组也跟着变换。
我们要定义四个数组一个是结果数组一个是原始下标数组一个是辅助数组也就是tmp记录改动过的顺序一个是下标辅助数组记录改动后的下标顺序。在while循环中每次更新tmp下标辅助数组也跟着更新。如果cur1大于cur2那么除了更新还需要往结果数组中写入个数要在当前元素的原始下标处写入个数这里最好要画图来理解画原始下标和下标变动后的图。在最后for循环中的排序除了原数组nums还有原始下标数组也要排序。 vectorint index;//原始元素下标vectorint res;//最终结果int tmp[500010];//排序辅助数组int tmpIndex[500010];//元素下标的辅助数组
public:vectorint countSmaller(vectorint nums) {int sz nums.size();index.resize(sz);res.resize(sz);for(int i 0; i sz; i){index[i] i;}mergeSort(nums, 0, sz - 1);return res;}void mergeSort(vectorint nums, int left, int right){if(left right) return ;int mid (left right) 1;mergeSort(nums, left, mid);mergeSort(nums, mid 1, right);int cur1 left, cur2 mid 1, i 0;while(cur1 mid cur2 right){if(nums[cur1] nums[cur2]){tmp[i] nums[cur2];tmpIndex[i] index[cur2];}else {res[index[cur1]] right - cur2 1;//经历了之前的排序index已经记录下了最新的下标变动这里就可以直接用cur1来获取正确的下标tmp[i] nums[cur1];tmpIndex[i] index[cur1];}}while(cur1 mid){tmp[i] nums[cur1];tmpIndex[i] index[cur1];}while(cur2 right){tmp[i] nums[cur2];tmpIndex[i] index[cur2];}for(int j left; j right; j){nums[j] tmp[j - left];index[j] tmpIndex[j - left];}}4、翻转对
493. 翻转对 还是一样的思路。左半部分右半部分然后一左一右。不过这里的条件不一样。这里的解决办法有两个一个是计算当前元素后面有多少元素的两倍比我小另一个是计算当前元素之前有多少元素的一半比我大这两个的高效顺序分别是降序和升序。
第一个思路cur1和cur2找当前元素的后面那就以cur1为重点如果cur2的2倍大于等于cur1cur2就往后走如果小于那么后面的肯定都小于。第二个思路cur1和cur2找当前元素的前面那就以cur2为重点如果cur1的一半比cur2小那么cur1后的肯定都符合条件如果cur1的一半大于cur2那cur1往后走。最后合并两个有序数组。 int tmp[50010];
public:int reversePairs(vectorint nums) {return mergeSort(nums, 0, nums.size() - 1);}int mergeSort(vectorint nums, int left, int right){if(left right) return 0;int ret 0;int mid (left right) 1;ret mergeSort(nums, left, mid);ret mergeSort(nums, mid 1, right); int cur1 left, cur2 mid 1, i left;//先计算翻转对0还是left都行/*while(cur1 mid)//这里排降序也可以排升序{while(cur2 right nums[cur2] nums[cur1] / 2.0) cur2;//2.0是为了防止除不尽if(cur2 right) break;ret right - cur2 1;cur1;}*/while(cur2 right)//升序{while(cur1 mid nums[cur2] nums[cur1] / 2.0) cur1;if(cur1 mid) break;ret mid - cur1 1;cur2;}cur1 left, cur2 mid 1;//归位一下开始排序while(cur1 mid cur2 right){tmp[i] nums[cur1] nums[cur2] ? nums[cur1] : nums[cur2];//tmp[i] nums[cur1] nums[cur2] ? nums[cur2] : 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 ret;}结束。
