README.md

面试题51. 数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

• 0 <= 数组长度 <= 50000

解法

在归并中统计逆序对。

Python3

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.res = 0

        def merge(part1, part2, nums):
            len1, len2 = len(part1) - 1, len(part2) - 1
            t = len(nums) - 1
            while len1 >= 0 and len2 >= 0:
                if part1[len1] > part2[len2]:
                    self.res += (len2 + 1)
                    nums[t] = part1[len1]
                    len1 -= 1
                else:
                    nums[t] = part2[len2]
                    len2 -= 1
                t -= 1
            while len1 >= 0:
                nums[t] = part1[len1]
                t -= 1
                len1 -= 1
            while len2 >= 0:
                nums[t] = part2[len2]
                t -= 1
                len2 -= 1

        def merge_sort(nums):
            if len(nums) < 2:
                return
            mid = len(nums) // 2
            s1, s2 = nums[:mid], nums[mid:]
            merge_sort(s1)
            merge_sort(s2)
            merge(s1, s2, nums)

        merge_sort(nums)
        return self.res

Java

class Solution {
    private int res = 0;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        mergeSort(nums, 0, n - 1);
        return res;
    }

    private void mergeSort(int[] nums, int s, int e) {
        if (s == e) {
            return;
        }
        int mid = s + ((e - s) >> 1);
        mergeSort(nums, s, mid);
        mergeSort(nums, mid + 1, e);
        merge(nums, s, mid, e);
    }

    private void merge(int[] nums, int s, int mid, int e) {
        int n = e - s + 1;
        int[] help = new int[n];
        int i = s, j = mid + 1, idx = 0;
        while (i <= mid && j <= e) {
            if (nums[i] > nums[j]) {
                res += (mid - i + 1);
                help[idx++] = nums[j++];
            } else {
                help[idx++] = nums[i++];
            }
        }
        while (i <= mid) {
            help[idx++] = nums[i++];
        }
        while (j <= e) {
            help[idx++] = nums[j++];
        }
        for (int t = 0; t < n; ++t) {
            nums[s + t] = help[t];
        }
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    if(!nums || nums.length < 2) return 0
    let res = 0
    function mergeSort(arr) {
        if(arr.length === 1) {
            return arr
        }
        let mid = ~~(arr.length/2)
        return merge(mergeSort(arr.slice(0,mid)),mergeSort(arr.slice(mid)))
    }
    function merge(a,b) {
        let r = []
        let cnt = 0
        while(a && b && a.length && b.length) {
            if(a[0] <= b[0]) {
                res += cnt
                r.push(a.shift())
            } else {
                r.push(b.shift())
                cnt++
            }
        }
        res += a.length * cnt
        return r.concat(a,b)
    }
    mergeSort(nums)
    return res
};

...