剑指offer_数组---数组中的逆序对

简介: 剑指offer_数组---数组中的逆序对

题目描述

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

/**
 * 
 */
package 数组;
/**
 * <p>
 * Title:InversePairs
 * </p>
 * <p>
 * Description:
 * </p>
 * 
 * @author 田茂林
 * @data 2017年8月14日 上午9:39:02
 */
public class InversePairs {
    /**
     * @param args
     */
    public int IntInversePairs(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int[] copy = new int[array.length]; // 辅助存储空间,里面的内容和array的是一样的.数组副本,用于归并排序
        /*for (int i = 0; i < array.length; i++) {
            copy[i] = array[i];
        }*/
        int count = InversePairsCore(array, copy, 0, array.length - 1);// 数值过大求余
        return count;
    }
    public int InversePairsCore(int[] array, int[] copy, int low, int high) {
        // 递归终止条件
        if (low >= high) {
            return 0;
        }
        // 递归
        int mid = (low + high) / 2;
        int leftCount = InversePairsCore(array, copy, low, mid) % 1000000007;
        int rightCount = InversePairsCore(array, copy, mid + 1, high) % 1000000007;
        // 核心部分,合并放入拷贝数组和进行逆序统计
        int count = 0;
        int left = mid;
        int right = high;
        int copyindex = high;
        // 合并子数组,并且统计逆序次数
        while (left >= low && right > mid) {
            if (array[left] > array[right]) {
                count += right - mid;
                copy[copyindex--] = array[left--];
                if (count >= 1000000007)// 数值过大求余
                {
                    count %= 1000000007;
                }
            } else {
                copy[copyindex--] = array[right--];
            }
        } // 比较两个已排好序的子数组,如果左边子数组的值大于右边的,说明逆序,次数为右边子数组的长度
            // 跳出循环的条件是,其中一个子数组已经全部放入了辅助数组空间,接下来把剩下子数组的数全部填充进去。
        for (; left >= low; left--) { // 右边子数组放置完毕
            copy[copyindex--] = array[left];
        }
        for (; right > mid; right--) { // 左边子数组放置完毕
            copy[copyindex--] = array[right];
        }
        for (int s = low; s <= high; s++) {  //统计好并且排好序后放入原数组,将原数组返回给上一层继续重复操作
            array[s] = copy[s];
        }
        return (leftCount + rightCount + count) % 1000000007;
    }
    public static void main(String[] args) {
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 0 };
        InversePairs inv = new InversePairs();
        System.out.println(inv.IntInversePairs(array));
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
        }
    }
}


相关文章
|
6月前
|
Java
每日一题《剑指offer》数组篇之数组中的逆序对
每日一题《剑指offer》数组篇之数组中的逆序对
41 0
每日一题《剑指offer》数组篇之数组中的逆序对
|
6月前
leetcode-922:按奇偶排序数组 II
leetcode-922:按奇偶排序数组 II
33 0
|
6月前
|
算法
LeetCode 922. 按奇偶排序数组 II
LeetCode 922. 按奇偶排序数组 II
41 0
|
C++
剑指offer 53. 数组中的逆序对
剑指offer 53. 数组中的逆序对
79 0
剑指offer 53. 数组中的逆序对
剑指offer 57. 数组中数值和下标相等的元素
剑指offer 57. 数组中数值和下标相等的元素
104 0
剑指offer 57. 数组中数值和下标相等的元素
剑指offer_数组---连续子数组的最大和
剑指offer_数组---连续子数组的最大和
46 0
剑指offer_数组---旋转数组的最小数字
剑指offer_数组---旋转数组的最小数字
42 0
剑指offer_数组---数组中只出现一次的数字
剑指offer_数组---数组中只出现一次的数字
69 0
剑指offer_数组---二维数组中的查找
剑指offer_数组---二维数组中的查找
59 0
剑指offer_数组---替换空格
剑指offer_数组---替换空格
45 0