牛客网 数组中的逆序对

题目:

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

解答:

最直接的想法,是两个for循环嵌套,求解所有的逆序对,但是复杂度太高。

后参考数组中的逆序对,利用了归并排序的想法,详细思路参照:【算法32】计算数组中的逆序对

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        res,count=self.mergerSort(data,0)
        count=count%1000000007
        return count
    def mergerSort(self,data,count):
        n=len(data)
        if n<=1:
            return data,count
        mid=n//2
        left,countl=self.mergerSort(data[:mid],count)
        right,countr=self.mergerSort(data[mid:],count)
        count=countl+countr
        ans=[]
        p=len(left)
        q=len(right)
        l,r=0,0
        while l<p and r<q:
            if left[l]<=right[r]:
                ans.append(left[l])
                l+=1
            else:
                ans.append(right[r])
                count=count+p-l
                r+=1
        ans+=left[l:]
        ans+=right[r:]
        return ans,count

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

C++STL中vector使用策略(一)

11750
来自专栏magicsoar

Effective Modern C++翻译(3)-条款2:明白auto类型推导

条款2 明白auto类型推导 如果你已经读完了条款1中有关模板类型推导的内容,那么你几乎已经知道了所有关于auto类型推导的事情,因为除了一个古怪的例外,aut...

197100
来自专栏猿人谷

C语言函数指针基础

本文写的非常详细,因为我想为初学者建立一个意识模型,来帮助他们理解函数指针的语法和基础。如果你不讨厌事无巨细,请尽情阅读吧。 函数指针虽然在语法上让人有些迷惑,...

431100
来自专栏程序生活

最大连续子序列和

https://blog.csdn.net/bitcarmanlee/article/details/51526010

10820
来自专栏数据结构与算法

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

30870
来自专栏大闲人柴毛毛

动态规划法(三)——最长公共子序列

问题描述 给定两个序列,求出它们的最长公共子序列。 如:序列X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a},则X和Y的最长公共子...

37140
来自专栏猿人谷

C++ STL算法系列3---求和:accumulate

 该算法在numeric头文件中定义。 假设vec是一个int型的vector对象,下面的代码: //sum the elements in vec start...

22580
来自专栏软件开发 -- 分享 互助 成长

使用数字进行字符遍历

有些时候使用数字进行遍历,然后将数字转化成需要的进制数,再将进制数对应成需要的字符是一种非常有效的方法。 如: 输入一个正整数X,在下面的等式左边的数字之间添加...

231100
来自专栏JavaEdge

美团18春招编程笔试题赏析1 字符串距离2 数字字符

34080
来自专栏机器学习算法工程师

算法题系列之二:求最大子数组之积

题目描述: 给定一个长度为N的整数数组,只允许用乘法,计算任意(N-1)个数的组合中乘积最大的一组。 算法分析: 动态规划的做法,假设数组为a[N],ma...

28660

扫码关注云+社区

领取腾讯云代金券