【LeetCode-数组】数组中的逆序对

标签：行合并   sort   个数   code   输入   pair   bin   数组   长度   

题目描述

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

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

说明： 0 题目链接： https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

思路1

暴力法。使用两层循环来做。代码如下：

class Solution {
public:
    int reversePairs(vector& nums) {
        if(nums.empty()) return 0;

        int cnt = 0;
        for(int i=0; inums[j]) cnt++;
            }
        }
        return cnt;
    }
};
// 超时

该方法超时。

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

思路2

使用归并排序来做。归并排序首先先将数组分为长度为 1 的子数组，然后两两进行合并。这题和归并排序的差别只有一行代码，我们在合并的时候，假设左边的数组为 [1, 3, 5]，右边的数组为 [2, 4]，现在左边数组的元素的下标 i 为 1，右边数组元素的下标 j 为 1，mid = 2，则我们可以找到 mid-i+1=2-1+1=2 个逆序对，分别是 (3, 2) 和 (5, 2)。所以我们在合并时，如果左边数组的元素大于右边数组的元素，我们就使用 mid-1+1 统计逆序对数，并加入到最终的答案当中。代码如下：

class Solution {
public:
    int reversePairs(vector& nums) {
        if(nums.empty()) return 0;

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

    void mergeSort(vector& nums, int left, int right){
        if(left& nums, int left, int mid, int right){
        vector temp(right-left+1, 0);
        int i = left;
        int j = mid+1;
        int k = 0;

        while(i

• 时间复杂度：O(nlogn)
• 空间复杂度：O(nlogn)

参考

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-dan-yi-dong-gui-bing-pai-xu-python-by-azl3979/

【LeetCode-数组】数组中的逆序对

标签：行合并   sort   个数   code   输入   pair   bin   数组   长度   

原文地址：https://www.cnblogs.com/flix/p/13377998.html