题意理解
给定一个数组,计算逆序对的个数
问题分析
用归并
归并和逆序怎么关联?每次两个有序序列合并,对于左边的最小值放入最后序列的适合,最后序列左边的,比它小的,都是和逆序关系。问题转化为计算左边最小值放入最后序列时,右边序列已处理的元素个数。
其他
力扣
链接
class Solution { public: int mergeSort(vector<int>& nums, vector<int>& tmps, int l, int h) { if (l >= h) return 0; int mid = (l + h) / 2; int vert = mergeSort(nums, tmps, l, mid) + mergeSort(nums, tmps, mid+1, h); int i = l, j = mid + 1, pos = l; while(i <= mid && j <= h) { if (nums[i] <= nums[j]) { tmps[pos] = nums[i]; i++; vert += j - (mid+1); } else { tmps[pos] = nums[j]; j++; } pos++; } while(i <= mid) { tmps[pos] = nums[i]; pos++; i++; vert += j - (mid+1); } while(j <= h) { tmps[pos] = nums[j]; pos++; j++; } copy(tmps.begin()+ l, tmps.begin() + h + 1, nums.begin() + l); return vert; } int reversePairs(vector<int>& nums) { int len = nums.size(); vector<int> tmps(len); return mergeSort(nums, tmps, 0, len-1); } };