【剑指offer】数组中的逆序对（校正书上错误）【归并排序】

太过爱你忘了你带给我的痛 2022-04-06 05:41 166阅读 0赞

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

> 题目保证输入的数组中没有的相同的数字

数据范围：

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

--------------------

## 算法思路 ##

归并排序可以用来寻找逆序对，时间复杂度为O(logN)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

## 书中代码的错误： ##

按照书上的算法，可以写出如下代码：

class Solution:
        def RecursionCount(self, data, copy, start, end):
            print(start, end, data, copy)
            if start >= end:
                copy[start] = data[start]
                return 0
            count = 0
            length = int((end - start) / 2)
            leftCount = self.RecursionCount(data, copy, start, start + length)
            rightCount = self.RecursionCount(data, copy, start + length + 1, end)
            #data = copy[:] #排序好之后，data要拷贝copy，才能保证data两边是排好序的。
            i, j = start + length, end
            copyIndex = end
            while i >= start and j >= start + length + 1:
                if data[i] > data[j]:
                    copy[copyIndex] = data[i]
                    copyIndex -= 1
                    i -= 1
                    count += (j - start - length)
                else:
                    copy[copyIndex] = data[j]
                    copyIndex -= 1
                    j -= 1
            #比较之后，可能有一边没遍历完，copy可能没被全部填满，需要继续填充copy
            while i >= start:
                copy[copyIndex] = data[i]
                copyIndex -= 1
                i -= 1
            while j >= start + length + 1:
                copy[copyIndex] = data[j]
                copyIndex -= 1
                j -= 1
            #data[start:end+1] = copy[start:end+1]
            print(start, end, data, copy)
            return leftCount + rightCount + count
        def InversePairs(self, data):
            # write code here
            if data == []:
                return 0
            copy = data[:]
            #copy = [0] * len(data)
            return self.RecursionCount(data, copy, 0, len(data) - 1)
    data = [7,5,6,4]
    print(Solution().InversePairs(data))

输出：

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

从输出可以看到，并没有输出正确的结果，也没有排序，原因是data数组并没排序好，copy数组是根据data数组排序的，但是data数组并没有在递归结束前有序。比如\[7, 5, 6, 4\] \[5, 7, 4, 6\]，5比4大的时候，将5作为copy的最后一个元素。最后输出\[6, 4, 7, 5\]。

--------------------

## 正确的解法(超时) ##

class Solution:
        def RecursionCount(self, data, copy, start, end):
            print(start, end, data, copy)
            if start >= end:
                copy[start] = data[start]
                return 0
            count = 0
            length = int((end - start) / 2)
            leftCount = self.RecursionCount(data, copy, start, start + length)
            rightCount = self.RecursionCount(data, copy, start + length + 1, end)
            data = copy[:]  #排序好之后，data要拷贝copy，才能保证data两边是排好序的。
            i, j = start + length, end
            copyIndex = end
            while i >= start and j >= start + length + 1:
                if data[i] > data[j]:
                    copy[copyIndex] = data[i]
                    copyIndex -= 1
                    i -= 1
                    count += (j - start - length)
                else:
                    copy[copyIndex] = data[j]
                    copyIndex -= 1
                    j -= 1
            #比较之后，可能有一边没遍历完，copy可能没被全部填满，需要继续填充copy
            while i >= start:
                copy[copyIndex] = data[i]
                copyIndex -= 1
                i -= 1
            while j >= start + length + 1:
                copy[copyIndex] = data[j]
                copyIndex -= 1
                j -= 1
            #data[start:end+1] = copy[start:end+1]
            print(start, end, data, copy)
            return leftCount + rightCount + count
        def InversePairs(self, data):
            # write code here
            if data == []:
                return 0
            copy = data[:]
            #copy = [0] * len(data)
            return (self.RecursionCount(data, copy, 0, len(data) - 1) % 1000000007)

但是这种解法会超时，造成时间复杂度过高，有两个原因：

1.  copy初始化没有必要完全拷贝data，可以随便初始化
2.  归并排序采用分治法，data与copy同步同样在递归的过程中，采用分治法的思想拷贝

--------------------

## 通过的代码 ##

class Solution:
        def RecursionCount(self, data, copy, start, end):
            #print(start, end, data, copy)
            if start >= end:
                copy[start] = data[start]
                return 0
            count = 0
            length = int((end - start) / 2)
            leftCount = self.RecursionCount(data, copy, start, start + length)
            rightCount = self.RecursionCount(data, copy, start + length + 1, end)
            #data = copy[:] #排序好之后，data要拷贝copy，才能保证data两边是排好序的。
            i, j = start + length, end
            copyIndex = end
            while i >= start and j >= start + length + 1:
                if data[i] > data[j]:
                    copy[copyIndex] = data[i]
                    copyIndex -= 1
                    i -= 1
                    count += (j - start - length)
                else:
                    copy[copyIndex] = data[j]
                    copyIndex -= 1
                    j -= 1
            #比较之后，可能有一边没遍历完，copy可能没被全部填满，需要继续填充copy
            while i >= start:
                copy[copyIndex] = data[i]
                copyIndex -= 1
                i -= 1
            while j >= start + length + 1:
                copy[copyIndex] = data[j]
                copyIndex -= 1
                j -= 1
            data[start:end+1] = copy[start:end+1]
            #print(start, end, data, copy)
            return leftCount + rightCount + count
        def InversePairs(self, data):
            # write code here
            if data == []:
                return 0
            #copy = data[:]
            copy = [0] * len(data)
            return (self.RecursionCount(data, copy, 0, len(data) - 1) % 1000000007)
    data = [7,5,6,4]
    print(Solution().InversePairs(data))

输出中间结果可以看到，将data数组使用了归并排序算法进行了排序：

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220406/27bf9916498d480b83e87623f62168df.png