class Solution {
public:
int reversePairs(vector<int>& nums) {
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int start, int end) {
if (start >= end) {
return 0;
}
int mid = (start + end) / 2;
int lc = mergeSort(nums, start, mid);
int rc = mergeSort(nums, mid + 1, end);
int cnt = count(nums, start, mid, end);
return lc + rc + cnt;
}
int count(vector<int>& nums, int start, int mid, int end) {
int l = start, r = mid + 1;
int count = 0;
while(l <= mid && r <= end){
if((long)nums[l] > (long)2 * nums[r]){
count += (mid - l + 1);
r++;
}else{
l++;
}
}
sort(nums.begin() + start, nums.begin() + end + 1);
return count;
}
};
19.Reverse Pairs
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
