wordpress 清除,wordpress中文主程序优化,怎么建立公司的网站吗,6度建筑人才网目录 1. 排序数组2. 交易逆序对的总数3. 计算右侧小于当前元素的个数4. 翻转对 1. 排序数组 算法思路: 本道题使用归并的思路进行排序, 先讲数组分为左右两个区间, 然后合并两个有序数组.
class Solution {vectorint tmp;
public:vectorint sortArray(vectorint tmp;
public:vectorint sortArray(vectorint nums) {tmp.reserve(nums.size());mergesort(nums,0,nums.size()-1);return nums;}void mergesort(vectorint nums,int left,int right){if(left right) return;int mid (right left)1;mergesort(nums,left,mid);mergesort(nums,mid1,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. 交易逆序对的总数 算法思路: 先找左半部分的逆序对, 然后再找右半部分的逆序对, 最后再一左一右的找逆序对, 找完左半部分和右半部分之后给数组排个序对数组的结果不影响, 而且排完序之后找一左一右的逆序对还简单些, 不由得我们就可以想到此方法和归并排序的思路一样, 只不过再排序的过程中增加了统计逆序对的个数. 这里可以采用两种策略, 第一种固定当前位置的值, 然后找前面有多少数是比我大的, 第二种策略, 固定当前位置的值, 找后面有多少元素是比我小的.
首先使用第一种策略, 固定一个数, 在前面找比我大的元素的个数. 当前为升序的排序, 我们归并的时候如果nums[cur1] nums[cur2] 时, 此时我们只需要把cur1就行, 如果nums[cur1]在某一个位置大于nums[cur2]时,此时已经找到了比nums[cur2]大的元素, 那么mid- cur1 1这段区间里面的所有值都比nums[cur2]大, 此时统计逆序对的数量即可, 然后再让cur2, 但是不要往了我们还要排序, 所以这一步写在归并数组那里即可. 那么既然升序可以, 降序可不可以呢? 如图所示, 该数组为降序的时候, 固定cur1, cur2位置时,如果cur1大于cur2则开始统计cur1中大于cur2元素的个数, 看似没有什么问题, 但是如果进入下一次循环中, cur1之后还有可能大于cur2,此时在统计那不是重复了嘛, 显然结果是错误的
第二种策略: 固定一个数, 然后找后面比我小的元素的个数 首先先来看降序的数组, 来统计固定一个位置之后, 后面有多少元素比我小, 当nums[cur1] nums[cur2]时, 此时不是我们想要的结果, 我们需要的是nums[cur1]nums[cur2], 这个时候, 我们统计后面有多少个元素比我小即可, 很显然此时数组是降序的, 所以right - cur2 1 即为结果
if(nums[cur1] nums[cur2]) tmp[i] nums[cur2]; else { ret right - cur2 1; tmp[i] nums[cur1]; }
反之我们来看一下升序 此时数组为升序, 我们需要找后面比前面小的元素的个数, 当固定到cur1之后, nums[cur1] nums[cur2]时, 此时开始找结果, 在后面看在mid到cur2之间的这部分都是比nums[cur1]小的, 但是下一次cur2之后还有可能是小于nums[cur1]的, 所以此时重复统计了 , 结果是错误的.
代码部分:
策略1
class Solution {int tmp[50000];
public:int reversePairs(vectorint record) {return mergeSort(record,0,record.size()-1);}int mergeSort(vectorint nums,int left,int right){if(leftright) return 0;int ret 0;int mid (right left) 1;ret mergeSort(nums,left,mid);ret mergeSort(nums,mid1,right);//程序到这里左边与右边已经处理完毕, 现在处理左右int cur1 left, cur2 mid 1, i 0;//升序 找比当前位置大的个数while(cur1 mid cur2 right){if(nums[cur1] nums[cur2])tmp[i] nums[cur1];else{ret mid - cur1 1;tmp[i] 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];}return ret;}
};策略2
class Solution {int tmp[50000];
public:int reversePairs(vectorint record) {return mergeSort(record,0,record.size()-1);}int mergeSort(vectorint nums,int left,int right){if(leftright) return 0;int ret 0;int mid (right left) 1;ret mergeSort(nums,left,mid);ret mergeSort(nums,mid1,right);//程序到这里左边与右边已经处理完毕, 现在处理左右int cur1 left, cur2 mid 1, i 0;//降序 找比当前位置小的个数while(cur1 mid cur2 right){if(nums[cur1] nums[cur2])tmp[i] nums[cur2];else{ret right - cur2 1;tmp[i] nums[cur1]; }}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];}return ret;}
};3. 计算右侧小于当前元素的个数 算法思路:
本道题更上一道题的思路是一模一样的, 上一道题我们采用了策略一的方法, 本道题我们采用策略二, 找后面比当前位置元素小的元素的个数, 但是与上一道题不同的是本道题要求返回对应位置的结果, 这是个问题, 如何解决呢, 我们可以采用哈希的思想, 如果使用哈希表那么如果遇到重复的元素, 我们就无法进行解决, 但是我们可以采用这种思想, 创建一个新的数组, 这个数组中存放的是对应位置原始的下标, 然后这个数组跟着nums一起变化, 但是无论怎样变换, 里面的下标还是最原始的下标位置. 编写代码:
class Solution {vectorint index;vectorint ret;int tmpNums[500010];int tmpIndxt[500010];
public:vectorint countSmaller(vectorint nums) {int n nums.size();ret.resize(n);index.resize(n);for(int i 0;i n;i)index[i] i;mergeSort(nums,0,n-1);return ret;}void mergeSort(vectorint nums,int left,int right){if(left right) return;int mid (left right)1;mergeSort(nums,left,mid);mergeSort(nums,mid1,right);//至此左右已经处理完, 现在处理一左一右int cur1 left, cur2 mid1, i 0;while(cur1 mid cur2 right){if(nums[cur1] nums[cur2]){tmpNums[i] nums[cur2];tmpIndxt[i] index[cur2];}else{ret[index[cur1]] right - cur2 1;tmpNums[i] nums[cur1];tmpIndxt[i] index[cur1];}}while(cur1 mid){tmpNums[i] nums[cur1];tmpIndxt[i] index[cur1];}while(cur2 right){tmpNums[i] nums[cur2];tmpIndxt[i] index[cur2];}for(int i left; i right; i){nums[i] tmpNums[i - left];index[i] tmpIndxt[i - left];}}
};4. 翻转对 算法思路:
首先我们还是先考虑两个策略. 策略一, 计算后面有多少个元素的两倍比我小, 策略二. 计算前面有多少元素的一半比我大. 不同于前两题, 本道题无法在归并的时候进行计算, 因为这里的比较逻辑和归并的比较逻辑是不同的, 所以这里我在归并逻辑之前采用双指针的方法先进行统计, 然后在进行归并排序. 那么首先来看策略一, 在处理完左右之后并排序之后, 我们处理一左一右的情况, 使用双指针, 计算后面有多少元素的两倍比我小, 如果nums[cur1] nums[cur2] * 2, 则说明后面元素的两倍比我大, 那么继续移动cur2, 知道找到cur2的位置两倍比我小, 然后进行统计, 此时cur1, 进行下一次的统计, 这里cur2还需要回退到mid1的位置嘛? 答案是不需要的, 因为当前位置cur2位置前面元素的两倍都是比我大的, 那cur1之后降序, 那么一定也是比我大的, 所以直接统计就可以了, 所以整体的时间复杂度为O(NlogN).
class Solution {int tmp[50000];
public:int reversePairs(vectorint nums) {return mergeSort(nums, 0 , nums.size() - 1);}int mergeSort(vectorintnums, 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,mid1,right);int cur1 left, cur2 mid 1, i left;while(cur1 mid){while(cur2 right nums[cur2] nums[cur1] / 2.0) cur2;if(cur2 right) break;//小优化ret right - cur2 1;cur1;}//降序cur1 left, cur2 mid 1;while(cur1 mid cur2 right)tmp[i] nums[cur1] nums[cur2] ? nums[cur1] : nums[cur2];while(cur1mid) tmp[i] nums[cur1];while(cur2right) tmp[i] nums[cur2];for(int j left; j right; j)nums[j] tmp[j]; return ret;}
};策略二: 找前面有多少元素的一半比我大 其实更策略一的逻辑是类似的, 只不过这里的数组是升序排列的, 找前面有多少元素的一半比我大, 先让cur1走, 如果/2之后大于nums[cur2]则, cur1, 找到位置之后统计ret, 然后让cur2,进行下一次的统计, 此时cur1也不需要回去, cur1之前的位置一半都是比cur2小的, 那么cur2之后一定还是比cur1小, 所以cur2直接即可.
class Solution {int tmp[50000];
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 mid (left right) 1;int ret 0;ret mergeSort(nums,left,mid);ret mergeSort(nums,mid1,right);int cur1 left, cur2 mid 1, i left;//升序, 先统计逆序对while(cur2 right){while(cur1 mid nums[cur1] / 2.0 nums[cur2]) 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];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;}
};完
