面试题51:数组中的逆序对

题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。例如:在数组{7,5,6,4}中，一共存在5个逆序对，分别是(7,6)、(7,5)、(7,4)、(6,4)和(5,4)。

解题思路

1. 使用归并排序对数组进行划分。

   
   image.png
2. 统计两个长度为2的子数组之间的逆序对
   定义两个变量分别指向第一段子数组的末尾i=mid和第二段子数组的末尾j=end，然后在保证i,j都有效的前提下，比较data[i]和data[j]值的大小。若data[i]>data[j]，则按照从大到小的顺序把data中的数据放入临时数组temp中，此时的逆序对为j-mid。(此时，子数组内部已排好序)
   image.png

代码

class Solution{
    public:
        
        long long InversePairsCore(vector<int>& data,vector<int>& temp,int start,int end)
        {
            if(start == end)
            {
                return 0;
            }
            int mid = (start+end)/2;
            long long left = InversePairsCore(temp,data,start,mid);
            long long right= InversePairsCore(temp,data,mid+1,end);
            long long count = 0;

            int indextemp = end;
            int i = mid;
            int j = end;

            while(i >= start && j >=mid+1)
            {
                if(data[i] > data[j])
                {
                    temp[indextemp--] = data[i--];
                    count += j-mid;
                }
                else
                {
                    temp[indextemp--] = data[j--];
                }
                cout << "temp中的元素" << temp[indextemp]<< " indextemp:" << indextemp <<endl;
            }

            for(;i>=start;i--)
            {
                temp[indextemp--] = data[i];
            }
            for(;j>=mid+1;j--)
            {
                temp[indextemp--] = data[j];
            }
            return left+right+count;
        }
        int InversePairs(vector<int> data)
        {
            int length = data.size();
            if(length<=0)
            {
                return 0;
            }
            vector<int> temp;
            for(int i =0;i<length;i++)
            {
                temp.push_back(data[i]);
            }

            long long result = InversePairsCore(data,temp,0,length-1);
            return result%1000000007;
        }

};

完整代码见Github