本问题对应的 leetcode 原文链接：剑指 Offer 51. 数组中的逆序对

问题描述

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

示例1 :

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

限制:

0 <= 数组长度 <= 50000

解题思路

视频讲解直达： 本题视频讲解

代码实现

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

    int mergeSort(int[] nums, int left, int right){
        if(left >= right){
            return 0;
        }
        int mid = (right - left) / 2 + left;
        int x1 = mergeSort(nums, left, mid);
        int x2 = mergeSort(nums, mid + 1, right);
        int x3 = merge(nums, left, mid, mid+1, right);

        return x1 + x2 + x3;
    }

    int merge(int[] nums, int l1, int r1, int l2, int r2){
        int[] temp = new int[r2 - l1 + 1];
        int count = 0;
        int i = l1, j = l2, k = 0;
        while(i <= r1 && j <= r2){
            if(nums[i] > nums[j]){
                count = count + (l2 - i);
                temp[k++] = nums[j++];
            }else{
                temp[k++] = nums[i++];
            }
        }
        while(i <= r1) temp[k++] = nums[i++];
        while(j <= r2) temp[k++] = nums[j++];

        // 把临时数组复制回原数组
        k = 0;
        for(i = l1; i <= r2; i++){
            nums[i] = temp[k++];
        }

        return count;
    }
}

复杂度和归并排序一样
时间：O(nlogn)
空间:O(n)

Python

class Solution(object):
    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) <= 1:
            return 0

        def mergeSort(left, right):
            if left >= right:
                return 0

            mid = (right - left) // 2 + left
            x1 = mergeSort(left, mid)
            x2 = mergeSort(mid + 1, right)

            i, j = left, mid + 1
            temp = []
            count = 0

            while i <= mid and j <= right:
                if nums[i] > nums[j]:
                    count += mid - i + 1
                    temp.append(nums[j])
                    j += 1
                else:
                    temp.append(nums[i])
                    i += 1

            while i <= mid:
                temp.append(nums[i])
                i += 1

            while j <= right:
                temp.append(nums[j])
                j += 1

            nums[left:right+1] = temp

            return x1 + x2 + count

        return mergeSort(0, len(nums) - 1)

C++

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        if (nums.empty() || nums.size() <= 1)
            return 0;

        function<int(int, int)> mergeSort;
        mergeSort = [&](int left, int right) -> int {
            if (left >= right)
                return 0;

            int mid = left + (right - left) / 2;
            int x1 = mergeSort(left, mid);
            int x2 = mergeSort(mid + 1, right);

            int i = left, j = mid + 1;
            int count = 0;
            vector<int> temp;

            while (i <= mid && j <= right) {
                if (nums[i] > nums[j]) {
                    count += mid - i + 1;
                    temp.push_back(nums[j]);
                    j++;
                } else {
                    temp.push_back(nums[i]);
                    i++;
                }
            }

            while (i <= mid) {
                temp.push_back(nums[i]);
                i++;
            }

            while (j <= right) {
                temp.push_back(nums[j]);
                j++;
            }

            for (int k = left; k <= right; k++) {
                nums[k] = temp[k - left];
            }

            return x1 + x2 + count;
        };

        return mergeSort(0, nums.size() - 1);
    }
};

Go

func reversePairs(nums []int) int {
    if len(nums) == 0 || len(nums) == 1 {
        return 0
    }

    var mergeSort func(int, int) int
    mergeSort = func(left, right int) int {
        if left >= right {
            return 0
        }

        mid := left + (right - left) / 2
        x1 := mergeSort(left, mid)
        x2 := mergeSort(mid + 1, right)

        i, j := left, mid + 1
        count := 0
        temp := make([]int, 0, right - left + 1)

        for i <= mid && j <= right {
            if nums[i] > nums[j] {
                count += mid - i + 1
                temp = append(temp, nums[j])
                j++
            } else {
                temp = append(temp, nums[i])
                i++
            }
        }

        for i <= mid {
            temp = append(temp, nums[i])
            i++
        }

        for j <= right {
            temp = append(temp, nums[j])
            j++
        }

        copy(nums[left:right+1], temp)

        return x1 + x2 + count
    }

    return mergeSort(0, len(nums) - 1)
}

JS

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    if (nums == null || nums.length <= 1) {
        return 0;
    }
    return mergeSort(nums, 0, nums.length - 1);
};

function mergeSort(nums, left, right) {
    if (left >= right) {
        return 0;
    }
    let mid = Math.floor((right - left) / 2 + left);
    let x1 = mergeSort(nums, left, mid);
    let x2 = mergeSort(nums, mid + 1, right);
    let x3 = merge(nums, left, mid, mid + 1, right);

    return x1 + x2 + x3;
}

function merge(nums, l1, r1, l2, r2) {
    let temp = new Array(r2 - l1 + 1);
    let count = 0;
    let i = l1,
        j = l2,
        k = 0;
    while (i <= r1 && j <= r2) {
        if (nums[i] > nums[j]) {
            count = count + (l2 - i);
            temp[k++] = nums[j++];
        } else {
            temp[k++] = nums[i++];
        }
    }
    while (i <= r1) temp[k++] = nums[i++];
    while (j <= r2) temp[k++] = nums[j++];

    // 把临时数组复制回原数组
    k = 0;
    for (i = l1; i <= r2; i++) {
        nums[i] = temp[k++];
    }

    return count;
}

shuaidi永久会员

收藏 海报挣佣金 推广链接