题解 | #数组中的逆序对#

问题描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。对于50%的数据,，对于100%的数据。

示例

输入：[1,2,3,4,5,6,7,0]

返回值：7

      题目保证输入的数组中没有的相同的数字，最直接的办法就是暴力搜索，设置内外两层循环，外层循环从开始元素到倒数第二个元素遍历，内层循环从开始位置的下一元素向后遍历，前面一个数字大于后面的数字，则这两个数字组成一个逆序对并计入总数中。但由于时间复杂度很大，该方法运行超时。

class Solution {
public:
    int InversePairs(vector<int> data) {
        int n=data.size();
        int sum=0;
        if(n<=1) return 0;
        for(int i=0;i<n-1;i++)//外层循环从开始元素到倒数第二个元素遍历
        {
            for(int j=i+1;j<n;j++)//内层循环从开始位置的下一元素向后遍历
            {
                if(data[i]>data[j])
                   { 
                    sum+=1;
                    sum %=1000000007;
                   }
                    
               
            }
        }
        return sum;
        
    }
};

• 时间复杂度：存在内外两层循环，时间复杂度为$O(n^2)$
• 空间复杂度:  借助一个辅助变量，空间复杂度为$O(1)$

方法二

       对照方法一我们必须提高算法的时间复杂度，因此使用归并排序的思想，首先介绍归并排序算法的思想：归并排序采用的是分治算法的思想，其中最重要的操作就是归并操作。 主要思想是，将数组平分为A，B两部分，分别将A,B两部分排好序，然后再合并，对A排序的时候，也是同样的思路，将A分为两份，同样先分别排序，再合并。首先对数组不断的一分为二，直到子数组中的元素个数为1，然后比较前后两个子数组中的值，如果前面数组中的元素大于后面数组中元素，那么找到一组逆序对，接着将两个数组进行合并，构成新的子数组，且该子数组是有序的，接着对子数组中有两个元素的前后子数组继续进行比较，前面的数组从右往左遍历，后面的数组从左往右遍历，分别对前后的元素进行比较，值得注意的是如果前面数组中某一元素小于后面数组某一元素，则不再进行比较，因为后面数组是升序排列的，此时前面数组向前遍历直接进行下一次的比较，直到合并后的数组为整个数组程序结束。

class Solution:
    def InversePairs(self, nums):
        # write code here
        if len(nums)<=1:
            return 0
        self.count = 0   
        self.merger(nums)
        return self.count%1000000007
    def merger(self, nums):
        if len(nums)==1:
            return nums
        middle = len(nums)>>1
        left = self.merger(nums[:middle])#归并排序左边子数组
        right = self.merger(nums[middle:])#归并排序右边子数组
        if left[-1]<= right[0]:
            return left+right       
        tmp = []#用于保存归并后的数组
        l, r = 0, 0             
        while len(left)>l and len(right)>r:#数组一分为二直到两个数组中各有一个元素
            if left[l]> right[r]:
                self.count += len(left)-l#在归并的过程中计算逆序对个数
                tmp.append(right[r])
                r += 1
            else:
                tmp.append(left[l])
                l += 1
        tmp.extend(left[l:]+right[r:])#合并两个子数组，合并后的数组也是有序的       
        return tmp

• 时间复杂度：使用归并排序的算法，因此时间复杂度为
• 空间复杂度:  归并后的数组需要保存，因此空间复杂度为$O(n)$