网站的风格分析,做网站什么行业前景好,企业网站建设对企业的宣传作用,wordpress如何做主页设置目录 1.排序数组
2.数组中的第K个最大元素
3.最小k个数
4.排序数组#xff08;归并#xff09;
5.数组中的逆序对
6.计算右侧小于当前元素的个数
7. 翻转对 1.排序数组 快排的写法有很多#xff0c;这里我采取了相对快的三路划分加随机基准值。 三路划分#xff0c;是…目录 1.排序数组
2.数组中的第K个最大元素
3.最小k个数
4.排序数组归并
5.数组中的逆序对
6.计算右侧小于当前元素的个数
7. 翻转对 1.排序数组 快排的写法有很多这里我采取了相对快的三路划分加随机基准值。 三路划分是将一段区间划成了【小于基准值】【等于基准值】【大于基准值】的三段区间。递归遍历的时候只需要递归【小于基准值】【大于基准值】的区间中间区间就可以看作已经完成了排序这也与二路划分的快排有很大区别相比之下遇到极端情况整个区间都是同一个数字时间复杂度会更小。 考虑到三路划分本身不是很难但是这边还是有基础题的。 75. 颜色分类 - 力扣LeetCode class Solution {
public:void sortColors(vectorint nums) {int nnums.size();int left-1,rightn;int index0;while(indexright){if(nums[index]0){swap(nums[left],nums[index]);}else if(nums[index]1)index;else if(nums[index]2){swap(nums[--right],nums[index]);}}}}; 283. 移动零 - 力扣LeetCode//这题是二路的但是思想跟三路很像主要是学会怎么划分具体是几路要看题目要求 void moveZeroes(int* nums, int numsSize) {int dest-1,cur0;while(curnumsSize){if(nums[cur]!0){dest;int tmpnums[dest];nums[dest]nums[cur];nums[cur]tmp;}cur;}
} 912. 排序数组 - 力扣LeetCode class Solution {
public:
//返回随机基准值int rad(vectorintnums,int left,int right){int rrand();return nums[r%(right-left1)left];}
//快排本身void fastsort(vectorintnums,int left,int right){if(leftright)return;//递归出口int midrad(nums,left,right);//获取基准值int lleft-1,rright1,index left;//设定三指针方便划分3路while(indexr){if(nums[index]mid)swap(nums[index],nums[l]);else if(nums[index]mid)index;else if(nums[index]mid)swap(nums[index],nums[--r]);}fastsort(nums,left,l);fastsort(nums,r,right);}vectorint sortArray(vectorint nums) {int nnums.size();srand(time(0));fastsort(nums,0,n-1); return nums;}
}; 2.数组中的第K个最大元素 215. 数组中的第K个最大元素 - 力扣LeetCode class Solution {
public:
//返回随机基准值int rad(vectorintnums,int left,int right){int rrand();return nums[r%(right-left1)left];}
//快排int qsort(vectorintnums,int left,int right,int k){
//结合最下面的条件判断我们会发现我们只会进入至少有一个元素的区间
//所以最多就是leftright我们在寻找最有可能的区间中一直找找到只有
//一个元素说明正好就是他了if(leftright)return nums[left];
//三路划分int midrad(nums,left,right);int indexleft,lleft-1,rright1;while(indexr){if(nums[index]mid)swap(nums[index],nums[l]);else if(nums[index]mid)index;else swap(nums[index],nums[--r]);}
//a是【小于基准值】的个数b是【等于基准值】的个数c是【大于基准值】的个数int al-left1,br-l-1,cright-r1;
//ck说明第k大的数一定在【大于基准值】区间里所以只需要递归这个区间即可if(ck){return qsort(nums,r,right,k);}
//在不满足ck的情况bck说明我们要找的第k大数正好就是当前的基准值
//直接返回基准值即可else if(bck)return mid;
//在不满足上面条件的情况下因为k肯定是小于整个区间大小的那么bck说明abck
//那么此时第k大的数就在【小于基准值】区间内注意了前面两个条件k都是原始的k
//那是因为可以确定【等于基准值】区间元素个数【大于基准值】区间元素个数大于k个或
//【大于基准值】区间元素个数大于k个所以k一定是在left-right区间内的
//但这里不同虽然我们可以判断第k大数在【小于基准值】区间内
//但是这个区间元素不一定大于等于k个所以我们传参的时候是在
//【小于基准值】区间内找第k-b-c大的数else{return qsort(nums,left,l,k-b-c);}}int findKthLargest(vectorint nums, int k) {int nnums.size();srand(time(NULL));return qsort(nums,0,n-1,k);}
}; 3.最小k个数 面试题 17.14. 最小K个数 - 力扣LeetCode class Solution {
public:int rad(vectorint arr,int l,int r){return arr[rand()%(r-l1)l];}void dfs(vectorint arr,int l,int r,int k){if(lr)return ;int keyrad(arr,l,r);int leftl-1,rightr1,indexl;while(indexright){if(arr[index]key)swap(arr[index],arr[left]);else if(arr[index]key)index;else swap(arr[index],arr[--right]);}int aleft-l1,bright-1-left,cr-right1;
//ak说明最小k个数一定在【小于基准值】的区间里。所以要继续递归a的区间
//然后三路划分a区间重复操作直到满足第二个条件。
//如果满足abk那么不管是ak还是abk都说明此时数组前k个数已经是最小的k个数了
//直接返回即可
//如果前两个条件都不满足说明这k个数是包含了a和b包含了部分c所以要继续递归c的区间
//然后三路划分c区间重复操作直到满足第二个条件。if(ak)dfs(arr,l,left,k);else if(abk)return ;else dfs(arr,right,r,k-a-b);}vectorint smallestK(vectorint arr, int k) {srand(time(NULL));dfs(arr,0,arr.size()-1,k);vectorintres(k);for(int i0;ik;i)res[i]arr[i];return res;}
}; 4.排序数组归并 912. 排序数组 - 力扣LeetCode class Solution {
public:void merge(vectorintnum,int l,int r){if(lr)return;int midl(r-l)/2;merge(num,l,mid);merge(num,mid1,r);int i1l,i2mid1;int i30;while(i1midi2r){if(num[i1]num[i2]){tmp[i3]num[i1];}else tmp[i3]num[i2];}while(i1mid)tmp[i3]num[i1];while(i2r)tmp[i3]num[i2];for(int il;ir;i)num[i]tmp[i-l];return ;}vectorint sortArray(vectorint nums) {tmp.resize(nums.size());merge(nums,0,nums.size()-1);return nums;}vectorinttmp;
}; 5.数组中的逆序对 数组中的逆序对_牛客题霸_牛客网 (nowcoder.com) 思路依旧是归并。 整个数组我们可以这样思考。一段区间的逆序对如果以中间划分可以分为【左部分】的逆序对个数【右部分】的逆序对个数【左部分挑一个,右部分挑一个】的逆序对个数 由此我们可以以分治的思路一路切割。 注意【左部分挑一个,右部分挑一个】这部分必须要依靠排序来快速挑选否则时间复杂度依旧是On2。 也就是说可以分为【左部分】的逆序对个数排序【右部分】的逆序对个数排序【左部分挑一个,右部分挑一个】的逆序对个数排序。 #include cstdio
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型vector * return int整型*/int tmp[100010]{0};int _InversePairs(vectorint nums,int l,int r){if(lr)return 0;//说明当前区间只有1或0个数字没有逆序对返回0int midl(r-l)/2;int res0;res_InversePairs(nums,l , mid);//加左部分res_InversePairs(nums, mid1, r);//加右部分res%1000000007;//题目数据要求必须mod不然有个样例会溢出int cur1l,cur2mid1;int il;while(cur1midcur2r)//排序和找逆序对同时进行{if(nums[cur1]nums[cur2])//说明自cur2坐标上起的数字都是比cur1坐标上的值小{res(r-cur21);tmp[i]nums[cur1];}else {tmp[i]nums[cur2];}}//sort(nums.begin()l,nums.begin()r1,greaterint());
//注意偷懒可以直接sort但是时间复杂度很高因为sort是Nlogn,而我们自己写
//有序数组合并可以做到Onwhile(cur1mid)tmp[i]nums[cur1];while(cur2r)tmp[i]nums[cur2];for(int kl;kr;k)nums[k]tmp[k];return res%1000000007;}int InversePairs(vectorint nums) {return _InversePairs(nums,0,nums.size()-1);}}; 6.计算右侧小于当前元素的个数 315. 计算右侧小于当前元素的个数 - 力扣LeetCode 这题跟上一题很像。 我们需要两个额外的数组一个是用来记录数字在原数字中的下标在排序时同步移动 一个是用来记录答案的数组。利用第一个数组即可下标访问及时更新第二个数组 class Solution {
public:void merge(vectorint nums,int l,int r,vectorintres){if(lr)return;int midl(r-l)/2;merge(nums,l,mid,res);merge(nums,mid1,r,res);int cur1l,cur2mid1,indexl;while(cur1midcur2r){if(nums[cur1]nums[cur2]){res[ix[cur1]](r-cur21);tmp[index]nums[cur1];tmp1[index]ix[cur1];}else{tmp[index]nums[cur2];tmp1[index]ix[cur2];}}while(cur1mid)tmp[index]nums[cur1],tmp1[index]ix[cur1];while(cur2r)tmp[index]nums[cur2],tmp1[index]ix[cur2];for(int il;ir;i)nums[i]tmp[i],ix[i]tmp1[i];}vectorint countSmaller(vectorint nums) {int nnums.size();for(int i0;in;i)ix[i]i;vectorintres(n,0);merge(nums,0,n-1,res);return res;}int ix[100100]{0};int tmp[100100]{0};int tmp1[100100]{0};
}; 7. 翻转对 493. 翻转对 - 力扣LeetCode 这题跟上面逆序对的写法几乎一模一样只是要注意排序必须单独写不能在找逆序对里同时排序。还有条件是2倍(虽然每个数都是int范围但是*2可能会溢出所以可以强转成更大的类型比如long,或者判断条件可以是ab/2.0注意c/是整除可能有余数所以要加个2.0这样就是浮点数了) class Solution {
public:int tmp[100010] { 0 };int _InversePairs(vectorint nums, int l, int r){if (l r)return 0;//说明当前区间只有1或0个数字没有逆序对返回0int mid l (r - l) / 2;int res 0;res _InversePairs(nums, l, mid);//加左部分res _InversePairs(nums, mid 1, r);//加右部分int cur1 l, cur2 mid 1;int i l;while (cur1 mid cur2 r)//排序和找逆序对同时进行{if (nums[cur1] 2*(long)nums[cur2])//说明自cur2坐标上起的数字都是比cur1坐标上的值小{res (r - cur2 1);cur1;}else {cur2;}}int l1l,l2mid1;while(l1midl2r){if(nums[l1]nums[l2]){tmp[i]nums[l1];}else{tmp[i]nums[l2];}}while(l1mid)tmp[i]nums[l1];while(l2r)tmp[i]nums[l2];for(int kl;kr;k)nums[k]tmp[k];return res;}int InversePairs(vectorint nums) {return _InversePairs(nums, 0, nums.size() - 1);}int reversePairs(vectorint nums) {return InversePairs(nums);}
};
