牛客 - 数组中的逆序对

描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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 here
        int 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或1
 
        int 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 here
        if (nums.empty()) return 0;
        vector<int> tmp(nums.size());
        return mergeSort(nums, tmp, 0, nums.size() - 1);
    }
};