题目地址：https://leetcode.com/PRoblems/reverse-pairs/?tab=Description
题目描述：Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].
You need to return the number of important reverse pairs in the given array.
*我的代码：
class Solution {public: int reverse_pairs(vector<long>& nums,int start,int end){ if(end-start<=1) return 0; int average=(start+end)/2,n=average; int count=reverse_pairs(nums,start,average)+reverse_pairs(nums,average,end); for(int i=start;i<average;i++){ while(n<end&&2*nums[n]<nums[i])n++; count+=(n-average); } inplace_merge(nums.begin()+start,nums.begin()+average,nums.begin()+end); return count; } int reversePairs(vector<int>& nums) { int n=nums.size(); vector<long> longnums; for(int i=0;i<n;i++) longnums.push_back(nums[i]); return reverse_pairs(longnums,0,n); }};解题思路： 同算法作业2 需注意一点是当nums中元素乘2时会溢出，因此需使用long。
新闻热点
疑难解答
