剑指offer(C++)-JZ51：数组中的逆序对(算法-排序)_剑指offer jz51-程序员宅基地

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P mod 1000000007
数据范围：对于 50% 的数据,size≤104
对于100% 的数据, size≤105

数组中所有数字的值满足 0≤val≤109

要求：空间复杂度 O(n)，时间复杂度O(nlogn)

示例：

输入：

[1,2,3,4,5,6,7,0]

返回值：

解题思路：

本题常规解题思路就是暴力法，但是本题要求复杂度为nlogn，那就可以用归并排序来解决了。

正常写一个归并排序。
在归并排序组合排序过程时，会把两子区间数据依次比较，重构新的顺序；此时如果左侧数值A大于右侧数值B，那就可以直接把A到中间位置C的数据个数直接累加。因为子区间已经完成排序，既然A都大于B了，那A到C之间所有的数据也必然大于B，所以可构成逆序对。
这样操作下来，时间复杂度满足题目要求了。

测试代码：

class Solution {
public:
    int mod = 1000000007;
    // 归并排序
    int mergeSort(vector<int>& data, int left, int right){
        // 停止
        if(left >= right)
            return 0;
        // 中间位
        int mid = (left + right) / 2;
        // 拆分合并，累加逆序对数量
        int count = mergeSort(data, left, mid) + mergeSort(data, mid + 1, right);
        count %= mod;
        // 排序
        int i = left, j = mid + 1;
        vector<int> temp(data);
        for(int t = left; t <= right; ++t){
            // i如果到了mid+1，说明左子区间遍历完毕，后续直接取右区间数据即可
            if(i == mid + 1){
                data[t] = temp[j];
                j++;
            }
            // j如果到了right+1，说明右子区间遍历完毕，后续直接取左区间数据即可
            // 如果左侧值小于右侧值，不符合逆序对，正常排序即可
            else if(j == right + 1 || temp[i] <= temp[j]){
                data[t] = temp[i];
                i++;
            }
            // 如果左侧值大于右侧值，说明左侧当前位置到左子区间结束的数值，都大于该右侧值，直接计算数量：mid-i+1；然后正常排序
            // 这样操作降低了时间复杂度
            else{
                data[t] = temp[j];
                j++;
                count += mid - i + 1;
            }
        }
        return count % mod;
    }
    // 逆序对
    int InversePairs(vector<int>& nums) {
        int size = static_cast<int>(nums.size());
        int count = mergeSort(nums, 0, size - 1);
        return count;
    }
};

本文链接：https://blog.csdn.net/zhaitianbao/article/details/131371768

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

python编码问题之encode、decode、codecs模块_python中encode在什么模块-程序员宅基地

文章浏览阅读2.1k次。原文链接先说说编解码问题编码转换时，通常需要以unicode作为中间编码，即先将其他编码的字符串解码（decode）成unicode，再从unicode编码（encode）成另一种编码。 Eg：str1.decode('gb2312') #将gb2312编码的字符串转换成unicode编码str2.encode('gb2312') #将unicode编码..._python中encode在什么模块

Java数据流-程序员宅基地

文章浏览阅读949次，点赞21次，收藏15次。本文介绍了Java中的数据输入流（DataInputStream）和数据输出流（DataOutputStream）的使用方法。

ie浏览器无法兼容的问题汇总_ie 浏览器 newdate-程序员宅基地

文章浏览阅读111次。ie无法兼容_ie 浏览器 newdate

想用K8s，还得先会Docker吗？其实完全没必要-程序员宅基地

文章浏览阅读239次。这篇文章把 Docker 和 K8s 的关系给大家做了一个解答，希望还在迟疑自己现有的知识储备能不能直接学 K8s 的，赶紧行动起来，K8s 是典型的入门有点难，后面越用越香。

ADI中文手册获取方法_adi 如何查看数据手册-程序员宅基地

文章浏览阅读561次。ADI中文手册获取方法_adi 如何查看数据手册

React 分页-程序员宅基地

文章浏览阅读1k次，点赞4次，收藏3次。React 获取接口数据实现分页效果以拼多多接口为例实现思路加载前加载动画加载后判断有内容的时候无内容的时候用到的知识点1、动画效果（用在加载前，加载之后就隐藏或关闭，用开关效果即可）2、axios请求3、map渲染页面4、分页插件（antd）代码实现import React, { Component } from 'react';//引入axiosimport axios from 'axios';//引入antd插件import { Pagination }_react 分页

随便推点

关于使用CryPtopp库进行RSA签名与验签的一些说明_cryptopp 签名-程序员宅基地

文章浏览阅读449次，点赞9次，收藏7次。这个变量与验签过程中的SignatureVerificationFilter::PUT_MESSAGE这个宏是对应的，SignatureVerificationFilter::PUT_MESSAGE，如果在签名过程中putMessage设置为true，则在验签过程中需要添加SignatureVerificationFilter::PUT_MESSAGE。项目中使用到了CryPtopp库进行RSA签名与验签，但是在使用过程中反复提示无效的数字签名。否则就会出现文章开头出现的数字签名无效。_cryptopp 签名