JZ51 数组中的逆序对

数组中的逆序对_牛客题霸_牛客网

描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围：  对于 50%50% 的数据, size≤104size≤104
对于 100%100% 的数据, size≤105size≤105

数组中所有数字的值满足 0≤val≤1090≤val≤109

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

输入描述：

题目保证输入的数组中没有的相同的数字

时间复杂度：用到归并排序O(nlogn),空间复杂度O(N)

先把数组分割成小小数组，统计出数组内部的逆序对的数目，然后再统计出两个相邻数组之间的逆序对数目。在统计逆序对的过程中，还要对数组进行排序。解题过程-P249

#include <algorithm>
#include <iterator>
#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型vector * @return int整型*/int cnt = 0;vector<int> copyNums;//如果把copyNums放到merge中进行copy，会超时int InversePairs(vector<int>& nums) {// write code herecopyNums.reserve(nums.size());mergeSort(nums, 0,  nums.size() - 1);// nums.swap(copyNums);return cnt;}void mergeSort(vector<int>&nums, int left, int right){if(left < right){int mid = left + (right - left)/2;mergeSort(nums, left, mid);mergeSort(nums, mid+1, right);merge(nums, left, mid, right);}}void merge(vector<int>& nums, int left, int mid, int right){int i = left, k = left, j = mid + 1;// vector<int> copyNums; //用copyNums来对比，这里会超时// copy(nums.begin(), nums.end(),back_inserter(nums));for(; i<= mid && j <= right; ++k){if(nums[i] < nums[j]){copyNums[k] = nums[i];++i;}else if(nums[i] > nums[j]){//题目没有重复的数字copyNums[k] = nums[j];++j;cnt += mid - i + 1;//// nums[i] > nums[j]，说明 nums[i...mid] 都大于 nums[j]if(cnt >= 1000000007) cnt %= 1000000007;//题目要求cnt>=1000000007,将cnt对1000000007取模的结果输出}}while(i <= mid) copyNums[k++] = nums[i++];while(j <= right) copyNums[k++]= nums[j++];for(k = left; k <= right; ++k){ //将排好序的数组写回numsnums[k] = copyNums[k];}}};