题解 | #数组中的逆序对#
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
class Solution { public: int mod = 1000000007; /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int mergeSort(vector<int>& nums, int l, int r, vector<int>& tem) { if (l >= r) { return 0; } int mid = l + (r - l) / 2; int res = mergeSort(nums, l, mid, tem) + mergeSort(nums, mid + 1, r, tem); res %= mod; int i = l; int j = mid + 1; copy(nums.begin() + l, nums.begin() + r + 1, tem.begin() + l); for (int k = l; k <= r; k++) { if (i == mid + 1) { //说明左边已经跑完,那就跑右边 nums[k] = tem[j]; j++; } else if(j == r+1 || tem[i] <=tem[j]) { nums[k] = tem[i]; i++; } else { nums[k] = tem[j]; j++; res += mid + 1 - i; } } res %=mod; return res; } int InversePairs(vector<int>& nums) { // write code here vector<int> tem(nums.size(),0); int res = mergeSort(nums, 0, nums.size()-1, tem); return res; } };
使用归并排序,求逆序对。如果左边数组的某个元素大于右边数组的某个元素,则逆序对增加mid + 1 - i, 其中i为做边元素的索引,mid为左边数组的最右边的索引。