将数组中的数逆序存放_python：35.数组中的逆序对

68 阅读 0 评论 45 点赞

我是靠谱客的博主勤恳小蘑菇，最近开发中收集的这篇文章主要介绍将数组中的数逆序存放_python：35.数组中的逆序对，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：

对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

示例1

输入

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

输出

解析

暴力解法

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here

        n = len(data)
        if data <= 1:
            return 0
        count = 0
        for i in range(n-1):
            for j in range(i+1, n):
                if data[i] > data[j]:
                    count += 1
        
        return count % 1000000007

2. 归并的改进版。

初识CV：python：归并排序zhuanlan.zhihu.com

先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个过程实际上就是归并排序。参考代码如下：

# -*- coding:utf-8 -*-
count = 0
class Solution:
    def InversePairs(self, data):
        global count
        def MergeSort(arr):
            global count
            n = len(arr)
            if n <= 1:
                return arr
            # 拆分
            mid = n // 2
            left = MergeSort(arr[:mid])
            right = MergeSort(arr[mid:])
            l, r = 0, 0
            res = []
            # 合并
            while l < len(left) and r < len(right):
                if left[l] <= right[r]:
                    res.append(left[l])
                    l += 1
                else:
                    res.append(right[r])
                    r += 1
                    count += len(left) - l # left[l:]中的数据都比right[r]的数据大
            # 将左边或者右边剩余的数拼接上去
            res += left[l:]
            res += right[r:]
            return res
        MergeSort(data)
        return count % 1000000007