描述

在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并將P對1000000007取模的結果輸出。 即輸出P mod 1000000007

數據范圍： 對于 50% 的數據, $$size\le 10^4$$，對于100% 的數據, $$size\le 10^5$$數組中所有數字的值滿足 $$0\le val\le 10^9$$
要求：空間復雜度 $$O(n)$$，時間復雜度 $$O(nlogn)$$

輸入描述：
題目保證輸入的數組中沒有的相同的數字

示例1
輸入：[1,2,3,4,5,6,7,0]
返回值：7

示例2
輸入：[1,2,3]
返回值：0

方法一：暴力方法

對于此題，按住一個arr[i], 依次判斷{i+1 … n-1]是否滿足條件。n為數組的大小。

class Solution {
public:/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可*** @param nums int整型vector* @return int整型*/const int m_nMod= 1000000007;int InversePairs(vector<int>& nums) {// write code hereint res = 0;for(int i = 0; i < nums.size();++i){for(int j = i + 1;j < nums.size(); ++j){if(nums.at(i) > nums.at(j)){res += 1;res %= m_nMod;}}}return res;}
};

方法二：歸并排序思想

方法思路

• ??分治策略??：使用歸并排序的思想，將數組分成兩個子數組，分別遞歸排序并統計子數組內的逆序對數量。
• ??合并階段統計逆序對??：在合并兩個有序子數組時，如果左子數組的當前元素大于右子數組的當前元素，則左子數組中當前元素及其之后的所有元素均能與右子數組的當前元素形成逆序對。
• ??輔助數組??：使用一個輔助數組在合并過程中存儲排序后的結果，以避免頻繁創建新數組。
• ??取模運算??：由于逆序對數量可能很大，每次累加后都需對 1000000007 取模，防止溢出。

class Solution {
public:/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** * @param nums int整型vector * @return int整型*/const int m_nMod = 1000000007;int mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r){if (l >= r) return 0;  // 遞歸終止：子數組長度為0或1int mid = l + (r - l) / 2;  // 防溢出計算中點long long count = 0;// 遞歸處理左右子數組并累加逆序對數count = (count + mergeSort(nums, tmp, l, mid)) % m_nMod;count = (count + mergeSort(nums, tmp, mid + 1, r)) % m_nMod;// 合并有序子數組并統計跨區逆序對int i = l, j = mid + 1, k = l;while (i <= mid && j <= r){if (nums[i] <= nums[j]){tmp[k++] = nums[i++];  // 無逆序對}else{tmp[k++] = nums[j++];// 關鍵：左半部分剩余元素均與nums[j]構成逆序對count = (count + (mid - i + 1)) % m_nMod;}}// 處理剩余元素while (i <= mid) tmp[k++] = nums[i++];while (j <= r) tmp[k++] = nums[j++];// 將排序結果復制回原數組for (int idx = l; idx <= r; ++idx) {nums[idx] = tmp[idx];}return count % m_nMod;}int InversePairs(vector<int>& nums) {// write code hereif (nums.empty()) return 0;vector<int> tmp(nums.size());return mergeSort(nums, tmp, 0, nums.size() - 1);}
};