JZ51 数组中的逆序对

题目

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

方法1：暴力

思路

算法实现
两个for循环，如果前面的数大于后面的计数加1即可

问题
当输入数过大时，需要的时间会很长，所以此方法不行

代码

package mid.JZ51数组中的逆序对;

import java.util.ArrayList;

public class Solution {
     public int InversePairs1(int[] array) {
            int k = 1000000007;
            if (array.length <= 1) return 0;
            int res = 0;
    
            for (int i = 1; i < array.length; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (array[i] < array[j])
                        res++;
                }
            }
            return res % k;
        }
}

方法2 归并排序思想

思路

• 先分：分呢，就是将数组分为两个子数组，两个子数组分为四个子数组，依次向下分，直到数组不能再分为止！
• 后并：并呢，就是从最小的数组按照顺序合并，从小到大或从大到小，依次向上合并，最后得到合并完的顺序数组！
• 归并统计法，关键点在于合并环节，在合并数组的时候，当发现右边的小于左边的时候，此时可以直接求出当前产生的逆序对的个数。

代码

package mid.JZ51数组中的逆序对;

import java.util.Arrays;

public class Solution {
    /**
     * 分治
     *
     * @param array
     * @return
     */
    public int count = 0;

    public int InversePairs(int[] array) {
        divMerge(array, 0, array.length-1);
        return count;
    }

    public void divMerge(int[] array, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        //分左边
        divMerge(array, left, mid);
        //分右边
        divMerge(array, mid + 1, right);

        //合并
        int i = left;
        int j = mid + 1;
        //临时数组
        int[] tmp = new int[right - left + 1];
        int k = 0;
        while (i <= mid && j <= right) {
            if (array[i] > array[j]) {
                tmp[k++] = array[j++];
                count += mid - i + 1;
                count %= 1000000007;
            } else {
                tmp[k++] = array[i++];
            }
        }
        while (i <= mid) {
            // 如果右边的走完了 就把左边的放到tmp后面
            tmp[k++] = array[i++];
        }

        while (j <= right) {
            // 如果左边的走完了 就把右边的放到tmp后面
            tmp[k++] = array[j++];
        }

        // 把排好序的tmp 移到 array中
        for(int l=0; l<k; l++) {
            array[left++] = tmp[l];
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().InversePairs(new int[]{1, 2, 3, 4, 5, 6, 7, 0}));
    }

    /**
     * 暴力
     *
     * @param array
     * @return
     */
    public int InversePairs1(int[] array) {
        int k = 1000000007;
        if (array.length <= 1) return 0;
        int res = 0;

        for (int i = 1; i < array.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (array[i] < array[j])
                    res++;
            }
        }
        return res % k;
    }
}