建设银行网站转账,湖北住房与城乡建设部网站,中国空间站机械臂,现在有什么有效的引流方法在数组中的两个数字#xff0c;如果前面一个数字大于后面的数字#xff0c;则这两个数字组成一个逆序对。输入一个数组#xff0c;求出这个数组中的逆序对的总数。 示例 1:
输入: [7,5,6,4] 输出: 5
限制#xff1a;
0 数组长度 50000
来源#xff1a;力扣…在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对的总数。 示例 1:
输入: [7,5,6,4] 输出: 5
限制
0 数组长度 50000
来源力扣LeetCode 链接https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
解题报告
今天没用树状数组写因为好久不练归并排序了得熟悉下记住它是有额外空间复杂度的。
注意点1最后的while里面别忘了也要统计cnt变量。
注意点2如果函数里是lr而不是lr的话就不需要特判num.size()0了
AC代码
class Solution {
public:int reversePairs(vectorint nums) {if(nums.size() 0) return 0;return mergesort(nums, 0, nums.size()-1);}int mergesort(vectorint nums, int l, int r) {int cnt 0;if(l r) return 0;int mid (lr)/2;//[l, mid] [mid1,r]cnt mergesort(nums, l, mid);cnt mergesort(nums, mid1, r);vectorint tmp;int p1 l, p2 mid1;while(p1 mid p2 r) {if(nums[p1] nums[p2]) {tmp.push_back(nums[p1]);p1;cnt p2 - (mid1); }else {tmp.push_back(nums[p2]);p2;}}while(p1 mid) {tmp.push_back(nums[p1]);cnt p2 - (mid1);}while(p2 r) tmp.push_back(nums[p2]);for(int i l; ir; i) {nums[i] tmp[i-l];}return cnt;}
};
