美文网首页剑指 Offer Java版
剑指Offer Java版 面试题51:数组中的逆序对

剑指Offer Java版 面试题51:数组中的逆序对

作者: 孙强Jimmy | 来源:发表于2019-08-03 15:41 被阅读24次

    题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出,即输出P%1000000007。例如,在数组{7, 5, 6, 4}中,一共存在5个逆序对,分别是(7, 6)、(7, 5)、(7, 4)、(6, 4)和(5, 4)。

    练习地址

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

    参考答案

    public class Solution {
        public int InversePairs(int[] array) {
            if (array == null || array.length == 0) {
                return 0;
            }
            int[] copy = new int[array.length];
            for (int i = 0; i < array.length; i++) {
                copy[i] = array[i];
            }
            return inverse(array, copy, 0, array.length - 1);
        }
        
        private int inverse(int[] array, int[] copy, int start, int end) {
            if (start == end) {
                return 0;
            }
            int mid = (start + end) / 2;
            int left = inverse(copy, array, start, mid);
            int right = inverse(copy, array, mid + 1, end);
            int leftIndex = mid, rightIndex = end, copyIndex = end, count = 0;
            while (leftIndex >= start && rightIndex > mid) {
                if (array[leftIndex] > array[rightIndex]) {
                    copy[copyIndex--] = array[leftIndex--];
                    count += rightIndex - mid;
                    if (count >= 1000000007) {
                        count %= 1000000007;
                    }
                } else {
                    copy[copyIndex--] = array[rightIndex--];
                }
            }
            while (leftIndex >= start) {
                copy[copyIndex--] = array[leftIndex--];
            }
            while (rightIndex > mid) {
                copy[copyIndex--] = array[rightIndex--];
            }
            return (left + right + count) % 1000000007;
        }
    }
    

    复杂度分析

    • 时间复杂度:O(nlogn)。
    • 空间复杂度:O(n)。

    👉剑指Offer Java版目录
    👉剑指Offer Java版专题

    相关文章

      网友评论

        本文标题:剑指Offer Java版 面试题51:数组中的逆序对

        本文链接:https://www.haomeiwen.com/subject/mpbjdctx.html