描述

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

方法一：归并

思路：通过归并处理，具体细节解释看注释
代码实现与相应解释说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
     //用于在归并时拷贝数组数据，便于排序。
     int[] temp;
     //原始数据
     int[] nums;
     int mod = 1000000007;

    public int InversePairs (int[] nums) {
    //如果数组为null或者为空数组，返回0
        if (nums == null || nums.length == 0) return 0;
        //初始化temp
        temp = new int[nums.length];
        this.nums = nums;
        //调用递归函数
        return mergeSort(0, nums.length-1);
    }

    int mergeSort(int left, int right) {
    	//结束递归的判断条件
        if (left >= right) return 0;
        //求得中间值
        int mid = (left + right) / 2;
        //调用递归函数，并且获取返回值
        int count = mergeSort(left, mid) + mergeSort(mid + 1, right);
        //处理结果，防止结果过大
        count %= mod;
        //拷贝nums数组
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        //获得数组右半部分的起始坐标
        int left2 = mid + 1;
        //由于数组的左半部分和右半部分，已经完成了递归，所以数组的左半部分是有序的，
        //右半部分也是有序的，并且已经拷贝到了temp数组。接下来这个循环就是将temp中的数字
        //经过比较后一个一个放入nums数组中，并且统计逆序对。
        for (int i = left; i <= right; i++) {
        //当left==mid+1，说明左半部分的数组数字已经遍历完成，所以只需要将右半部分的有序数组
        //依次填入。
            if (left == mid + 1) 
            nums[i] = temp[left2++];
            //当left2==right+1，说明右半部分数组填充完毕，需要将左半部分数组依次填入。
            //或者当temp[left] <= temp[left2]，说明左边的数值小于右边的数值，应当先填入左边的
            //数值
            else if (left2 == right + 1 || temp[left] <= temp[left2]) nums[i] = temp[left++];
            //当右边的数值小于左边的数值，说明出现逆序对，先填入右边的数值，并且计算逆序对个数。
            //count说明：因为在数组的右半部分和左半部分是各自有序的，右半部分后面的数字大于或等于右半部分前面
            /的数字，左半部分同理。所以当出现右面的数字小于左边的数字时候，因为右面的这个数字肯定大于在右半部分中，位置在
            //自己前面的数字，所以这部分不用计算。但是它也肯定小于左半部分中，位置在左边这个数字之后的数字，这部分需要计算
            //并且不能忘记左边这个数字本身
            else {
                nums[i] = temp[left2++];
                count += mid - left + 1;
            }
        }
        return count % mod;
            
    
    
    }
}