0%

机试——数组中的逆序对

发表于 更新于 阅读次数： Valine：
本文字数： 363 阅读时长 ≈ 1 分钟

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

实例:

​ 输入：1,2,3,4,5,6,7,0

​ 输出：7

https://blog.csdn.net/lzq20115395/article/details/79554591

解法一：暴力冒泡

​ 这种方法比较简单，但是时间复杂度为O(n^2),这里不做详细阐述

解法二：归并法

​ 完全按照归并排序的方式来进行，只是附加上一个全局变量，来记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
global count
count = 0
def InversePairs(data):
    
    def core(data):
        # write code here
        if len(data) <= 1:
            return data
        num = int(len(data) / 2)

        left = core(data[:num])
        right =core(data[num:])
        return Merge(left, right)
    core(data)
    
    return count

#合并各个子数组
def Merge(left, right):
        global count
        l1 = len(left)-1
        l2 = len(right)-1
        
        res = []
        num = 0
        while l1>=0 and l2>=0:
            if left[l1]<=right[l2]:
                res = [right[l2]]+res
                l2-=1
            else:
                res  = [left[l1]]+res
                count += l2+1
                l1-=1
        while l1>=0:
            res  = [left[l1]]+res
            l1-=1
        while l2>=0:
            res = [right[l2]]+res
            l2-=1
        
        return res

解法3：

​ 先将原来数组进行排序，然后从排完序的数据中去取出最小的，他在原数组中的位置能表示有多少比他大的数在他前面，每取出一个在原数组中删除该元素，保证后面去除的元素在原数组中是最小的，这样