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

数组中的逆序对

http://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5

题目：数组中的逆序对

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

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

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

解法一：

思路分析：首先使用暴力法去分析和思考问题，因为逆序对满足的条件为，前面的一个数字大于后面的数字，则这两个数字就组成了一个逆序对，所以用暴力法可以很方便的解决问题。

设定两个指针，分别为i和j，使用定i变j法进行判断和计数逆序对的个数。

1	2	3	4	5	6	7	0
i	j
将j循环一整遍，可以得到1和0之间构成一个逆序对，以此类推
	i	j
一直进行判断，最后得出count的值

具体C++代码为：

class Solution {
public:
    int InversePairs(vector<int> data) {
        int count = 0;
        int len = data.size();
        for(int i = 0;i < len ;++i){
            for(int j = i + 1;j < len;j){
                if(data[i] > data[j]){
                    count++;
                    count = count % 1000000007;
                }
            }
        }
        return count;
    }
};

在该算法中，对于10^5的数据，该算***显示运行超时。

其时间复杂度为O(n^2)，空间复杂度为O(1)。

解法二：

思路分析：归并排序思想，将两个有序的数列合并成为一个大的有序的序列，通过不断递归，层层合并，就被称做归并。

假设有4个数字，分别为7，3，5，4，下边进行归并排序的图示演示：

将4个数字分为两组数据，分别为（7，3）和（5，4）。

具体实例分析：输入：[1,2,3,4,5,6,7,0]，返回值：7

图示：

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

具体程序如下所示：

public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        Sort(array, 0, array.length - 1);
        return count;
    }
    
    //归并排序
    public void Sort(int[] nums, int start, int end) {
        if (start < end) {
            int mid = start + ((end - start) >> 1);
            Sort(nums, start, mid);
            Sort(nums, mid + 1, end);
            //合并操作
            merge(nums, start, mid, end);
        }
    }
    
    public void merge(int[] nums, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (nums[p1] <= nums[p2]) {
                temp[p++] = nums[p1++];
            } else {
                //此时就是nums[p1]>nums[p2]的时候，组成逆序对
                //数量是mid-p1+1
                count = count + mid - p1 + 1;
                temp[p++] = nums[p2++];
            }
        }
        while (p1 <= mid) {
            temp[p++] = nums[p1++];
        }
        while (p2 <= end) {
            temp[p++] = nums[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
            nums[i + start] = temp[i];
        }
    }
}

时间复杂度为：O(N*logN)，

空间复杂度为O(N)。

算法自然分析文章被收录于专栏

在解决问题的同时，不断与人交流学习，通过牛客各式各样的题目，学习分享。