专业版装修用什么网站做导航条,门户网站建设,网上做的比较好的竞彩网站,网站首页设计尺寸文章目录 1、排序数组2、交易逆序对的总数3、计算右侧小于当前元素的个数4、翻转对 1、排序数组 给你一个整数数组 nums#xff0c;请你将该数组升序排列。 class Solution {
public:vectorint tmp;void mergeSort(vectorint nums,int left,int right){… 文章目录 1、排序数组2、交易逆序对的总数3、计算右侧小于当前元素的个数4、翻转对 1、排序数组 给你一个整数数组 nums请你将该数组升序排列。 class Solution {
public:vectorint tmp;void mergeSort(vectorint nums,int left,int right){if(leftright)return ;int mid(leftright)1;//对于非负整数并且不产生溢出的情况下//(left right) 1 和 (leftright)/2是等价的。mergeSort(nums,left,mid);mergeSort(nums,mid1,right);int cur1left,cur2mid1;int i0;while(cur1midcur2right){if(nums[cur1]nums[cur2]) tmp[i]nums[cur1];else tmp[i]nums[cur2];}//处理没有结束的while(cur1mid) tmp[i]nums[cur1];while(cur2right) tmp[i]nums[cur2]; for(int ileft;iright;i)nums[i]tmp[i-left];}vectorint sortArray(vectorint nums) {tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);return nums;}
};2、交易逆序对的总数 在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录 record返回其中存在的「交易逆序对」总数。 class Solution {
public:int tmp[50010];int mergeSort(vectorint nums,int left,int right){if(leftright)return 0;int ret0;//计数int mid(leftright)1;retmergeSort(nums,left,mid);retmergeSort(nums,mid1,right);int cur1left,cur2mid1;int i0;while(cur1midcur2right){if(nums[cur1]nums[cur2])tmp[i]nums[cur1];else{retmid-cur11;tmp[i]nums[cur2];}}//处理没有结束的while(cur1mid) tmp[i]nums[cur1];while(cur2right) tmp[i]nums[cur2]; for(int ileft;iright;i)nums[i]tmp[i-left];return ret;}int reversePairs(vectorint record) {return mergeSort(record,0,record.size()-1);}
};3、计算右侧小于当前元素的个数 给你一个整数数组 nums 按要求返回一个新数组 counts 。数组 counts 有该性质 counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 class Solution {
public:vectorint ret;vectorint index; // 记录 nums 中当前元素的原始下标int tmpNums[500010];int tmpIndex[500010];vectorint countSmaller(vectorint nums) {ret.resize(nums.size());index.resize(nums.size());for(int i0;inums.size();i)index[i]i;mergeSort(nums,0,nums.size()-1);return ret;}void mergeSort(vectorint nums,int left,int right){if(leftright)return;int mid(leftright)1;mergeSort(nums,left,mid);mergeSort(nums,mid1,right);int cur1left,cur2mid1,i0;while(cur1midcur2right){if(nums[cur1]nums[cur2]){tmpNums[i]nums[cur2];tmpIndex[i]index[cur2];}else{ret[index[cur1]]right-cur21;tmpNums[i]nums[cur1];tmpIndex[i]index[cur1];}}while(cur1mid){tmpNums[i]nums[cur1];tmpIndex[i]index[cur1];}while(cur2right){tmpNums[i]nums[cur2];tmpIndex[i]index[cur2];}for(int ileft;iright;i){nums[i]tmpNums[i-left];index[i]tmpIndex[i-left];}}
};4、翻转对 给定一个数组 nums 如果 i j 且 nums[i] 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。 class Solution {
public:int tmp[50010];int ret0;int reversePairs(vectorint nums) {mergeSort(nums,0,nums.size()-1);return ret; }void mergeSort(vectorint nums,int left,int right){if(leftright)return;int mid(leftright)1;mergeSort(nums,left,mid);mergeSort(nums,mid1,right);int cur1left,cur2mid1,i0;while(cur1midcur2right){if(nums[cur1]/2.0nums[cur2])cur2;else{retright-cur21;cur1;}}//排序是要按大小进行的并不是if(nums[cur1]/2.0nums[cur2])所以就不能在一起排序要分开cur1left,cur2mid1,i0;while(cur1midcur2right){if(nums[cur1]nums[cur2])tmp[i]nums[cur2];elsetmp[i]nums[cur1];}while(cur1mid)tmp[i]nums[cur1];while(cur2right)tmp[i]nums[cur2];for(int ileft;iright;i)nums[i]tmp[i-left];}
};
