微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 51. 数组中的逆序对

剑指offer 51. 数组中的逆序对

题目描述

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

算法

(归并排序) O(nlogn)

归并排序的过程中计算逆序对的数量，更精细的来说是在合并两个有序序列时计算逆序对的数量，对于两个有序序列，如 \\{4, 5\\} 和 \\{1, 2\\}，i 和 j 指向序列的第一个元素 i = 0, j = 3, mid = 1，对于 1 可以构成两个逆序对 <4, 1> 和 <5, 1> 即 mid - i + 1 = 2，同样对于 2 也有两个逆序对 <4, 2> 和 <5, 2>，即 mid - i + 1 = 2。

mid – i + 1 表示的是区间 [i, mid] 的长度，依然拿上面的例子看，对于 4 来说，4 可以和 1 构成逆序对，由于是有序序列，那么 4 之后的数同样也可以和 1 构成逆序对，即区间 [i, mid] 的元素个数就是和 j 可以构成的逆序对个数$。

所以当 nums[i] > nums[j] 时更新逆序对的数量即可。

时间复杂度

归并排序的时间复杂度为 O(nlogn)。

空间复杂度

临时数组需要 O(n) 的空间。

C++ 代码

class Solution {
public:
    int merge(vector<int>& nums, vector<int>& tmp, int l, int r) {
        if (l >= r) return 0;
        int mid = l + r >> 1;
        int res = merge(nums, tmp, l, mid) + merge(nums, tmp, mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) tmp[k ++ ] = nums[i ++ ];
            else { // nums[i] > nums[j]，则 [i, mid] 和 j 都可以构成逆序对
                res += mid - i + 1;
                tmp[k ++ ] = nums[j ++ ];
            }
        }

        while (i <= mid) tmp[k ++ ] = nums[i ++ ];
        while (j <= r) tmp[k ++ ] = nums[j ++ ];

        for (int i = l, k = 0; i <= r; i ++ ) nums[i] = tmp[k ++ ];
        return res;
    }

    int reversePairs(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> tmp(nums.size());
        return merge(nums, tmp, 0, nums.size() - 1);
    }
};

Java 代码

class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] tmp = new int[nums.length];
        return merge(nums, tmp, 0, nums.length - 1);
    }
    
    private int merge(int[] nums, int[] tmp, int l, int r) {
        if (l >= r) {
            return 0;
        }
        int mid = l + (r - l) / 2;
        int res = merge(nums, tmp, l, mid) + merge(nums, tmp, mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[k ++ ] = nums[i ++ ];
            } else {
                res += mid - i + 1;
                tmp[k ++ ] = nums[j ++ ];
            }
        }
        while (i <= mid) {
            tmp[k ++ ] = nums[i ++ ];
        }
        while (j <= r) {
            tmp[k ++ ] = nums[j ++ ];
        }
        for (i = l, k = 0; i <= r; i ++, k ++ ) {
            nums[i] = tmp[k];
        }
        return res;
    }
}

Python 代码

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if not nums:
            return 0
        tmp = [0] * len(nums)
        return self.merge(nums, tmp, 0, len(nums) - 1)
    
    def merge(self, nums: List[int], tmp: List[int], l: int, r: int) -> int:
        if l >= r:
            return 0
        mid = (l + r) // 2
        res = self.merge(nums, tmp, l, mid) + self.merge(nums, tmp, mid + 1, r)
        i, j, k = l, mid + 1, 0
        while i <= mid and j <= r:
            if nums[i] <= nums[j]:
                tmp[k] = nums[i]
                i += 1
            else:
                res += mid - i + 1
                tmp[k] = nums[j]
                j += 1
            k += 1
        while i <= mid:
            tmp[k] = nums[i]
            i += 1
            k += 1
        while j <= r:
            tmp[k] = nums[j]
            j += 1
            k += 1
        for i in range(l, r + 1):
            nums[i] = tmp[i - l]
        return res

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer