美文网首页【python剑指offer】
【python】剑指offer,数组中的逆序对?

【python】剑指offer,数组中的逆序对?

作者: 阿牛02 | 来源:发表于2019-07-29 08:04 被阅读0次

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

即输出P%1000000007

分析:

code:

import math

class Solution:   

    def InversePairs(self, data):       

        # write code here       

        count = 0       

        if len(data)==1:           

            return 0       

        if len(data) == 2:           

            if data[0]>data[1]:               

                return 1           

            else:               

                return 0       

        if len(data) > 2:           

            mid = (len(data)-1)//2         

            data_l = data[:mid]           

            data_r = data[mid:]           

            data_sorted_l = sorted(data_l)           

            data_sorted_r = sorted(data_r)         

            for i in range(len(data_sorted_r)):               

                for j in range(len(data_sorted_l)):                   

                    if data_sorted_l[j] > data_sorted_r[i]:                       

                        count += 1       

        return (count + self.InversePairs(data_l)+self.InversePairs(data_r))%1000000007

相关文章

网友评论

    本文标题:【python】剑指offer,数组中的逆序对?

    本文链接:https://www.haomeiwen.com/subject/tsycrctx.html