剑指 Offer 51. 数组中的逆序对 [hard]

剑指 Offer 51. 数组中的逆序对 [hard]

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

• 0 <= 数组长度 <= 50000

通过次数29,955 | 提交次数65,640

Second Try

2020-07-23

在second try里考虑了与first try不同的另一种处理方法，在右边插入的时候进行计数，结果直接掉大坑里了。因为右边插入的时候计数，其实把left没被处理的都算进去了。因此在最后两边有一边结束的时候，不再需要统计逆序对，都在前面统计过了。

一些理所当然的写法，总是引入一些莫名其妙的bug。。。

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        
        def merge_sort(nums, lft, rt):
            if lft + 1 >= rt:  # 有效index是[lft, rt-1]
                return 0  
            mid = (lft + rt) // 2
            c1 = merge_sort(nums, lft, mid)
            c2 = merge_sort(nums, mid, rt)
            c3 = 0 
            tmp = []
            lft_p, rt_p = lft, mid 
            while (lft_p < mid and rt_p < rt):
                if nums[lft_p] <= nums[rt_p]:  # 等号放在这里防止多计数
                    tmp.append(nums[lft_p])
                    lft_p += 1
                elif nums[lft_p] > nums[rt_p]:
                    tmp.append(nums[rt_p])
                    rt_p += 1
                    c3 += (mid - lft_p)  # 在右边插入的时候处理，需要考虑还有多少左边没被处理，这些没被处理的都比它大
            if lft_p == mid:
                tmp.extend(nums[rt_p:rt])  # 只剩下右边处理的时候，左边的都已经处理完了，c3 + 0 
            else:
                tmp.extend(nums[lft_p: mid])
                # 在只剩下左边代处理的时候，其逆序对已经被前面插入的right给处理完了，因此也不用特殊处理了
                # c3 += (rt - mid) * (mid - lft_p) #总共有多少个元素，每个元素前面的都有（rt-mid)个比它小的
            nums[lft:rt] = tmp  # 使用了辅助数组，然后再进行替换
            return c1 + c2 + c3 
        
        rv = merge_sort(nums, 0, len(nums))
        return rv 
            

• 执行用时：1548 ms, 在所有 Python3 提交中击败了81.79%的用户
• 内存消耗：19.1 MB, 在所有 Python3 提交中击败了100.00%的用户

• bug version

错误写法，在左右侧某一段结束之后，不需要更新逆序对统计了，因为都在right插入的时候统计了。right插入的时候，统计的都是未来left要处理的元素。

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        
        def merge_sort(nums, lft, rt):
            if lft + 1 >= rt:  # 有效index是[lft, rt-1]
                return 0  
            mid = (lft + rt) // 2
            c1 = merge_sort(nums, lft, mid)
            c2 = merge_sort(nums, mid, rt)
            c3 = 0 
            tmp = []
            lft_p, rt_p = lft, mid 
            while (lft_p < mid and rt_p < rt):
                if nums[lft_p] <= nums[rt_p]:  # 等号放在这里防止多计数
                    tmp.append(nums[lft_p])
                    lft_p += 1
                elif nums[lft_p] > nums[rt_p]:
                    tmp.append(nums[rt_p])
                    rt_p += 1
                    c3 += (mid - lft_p)  # 在右边插入的时候处理，需要考虑还有多少左边没被处理，这些没被处理的都比它大
            if lft_p == mid:
                tmp.extend(nums[rt_p:rt])
            else:
                tmp.extend(nums[lft_p: mid])
                c3 += (rt - mid) * (mid - lft_p) #总共有多少个元素，每个元素前面的都有（rt-mid)个比它小的
            nums[lft:rt] = tmp  # 使用了辅助数组，然后再进行替换
            return c1 + c2 + c3 
        
        rv = merge_sort(nums, 0, len(nums))
        return rv 

First Try

2020-07-23

看到这种题肯定先无脑冒泡法来一遍，数组长度到50k一波果然超时了，看题解清一色都是merge sort，还都说这是经典套路题了。 怎么这么多所谓的经典套路，结果我都没遇见过，还是naive啊。

瞥到merge sort关键词后，还是想不懂该怎么处理，详细看题解才知道原理。

merge sort在递归过程中，其实也是从左到右逐渐有序的。那么只要判断在排序过程中，出现多少个逆序对就可以了，有效利用了排序数组的特性，不用一个个去比较。

重点变成了如何在merge sort中，统计逆序对，是在左边插入过程还是在右边插入过程？ 在左边插入过程，则需要看已经有序的数组里面有多少个是右边的元素，看右边指针移动了多少距离即可（真是巧妙）。右边插入过程，则是看左边还有多少没被插入，看左边指针还有多久到终点。anyway，通过两个移动指针来操作，事情和逻辑变得简单了许多，merge sort看起来也清晰了许多。 虽然merge sort没有实现原地排序，使用辅助数组，但思路清晰最重要

还有个特殊点，就是当左边和右边相等的时候，是先插入左边还是右边，计数如何处理？大概考虑下就知道了，如果是通过左边插入过程来考虑，那么等号时候要先插入左边，防止相同的右边提前放在前面增加了计数。如果是通过右边插入过程来考虑，说起来也需要先放入左边。这么看来都是提前放入左边。 本来在merge sort里无关紧要的地方，在这里就需要特殊处理。

在second try里考虑了另一种处理方法，在右边插入的时候进行计数，结果直接掉大坑里了。因为右边插入的时候计数，其实把left没被处理的都算进去了。因此在最后两边有一边结束的时候，不再需要统计逆序对，都在前面统计过了。具体看下second try的代码。 一些理所当然的写法，总是引入一些莫名其妙的bug。。。

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        

        def merge_sort(nums, lft, rt):
            if lft + 1 >= rt:  # 有效index是[lft, rt-1]
                return 0  
            mid = (lft + rt) // 2
            c1 = merge_sort(nums, lft, mid)
            c2 = merge_sort(nums, mid, rt)
            c3 = 0 
            tmp = []
            lft_p, rt_p = lft, mid 
            while (lft_p < mid and rt_p < rt):
                if nums[lft_p] <= nums[rt_p]:  # 等号放在这里防止多计数
                    tmp.append(nums[lft_p])
                    lft_p += 1
                    # 每次左边比较小的放上去，可以在这时候看到右边已经有多少比它小的元素，并进行计数
                    c3 += (rt_p - mid)
                elif nums[lft_p] > nums[rt_p]:
                    tmp.append(nums[rt_p])
                    rt_p += 1
            if lft_p == mid:
                tmp.extend(nums[rt_p:rt])
            else:
                tmp.extend(nums[lft_p: mid])
                c3 += (rt - mid) * (mid - lft_p) #总共有多少个元素，每个元素前面的都有（rt-mid)个比它小的
            nums[lft:rt] = tmp  # 使用了辅助数组，然后再进行替换
            return c1 + c2 + c3 
        
        rv = merge_sort(nums, 0, len(nums))
        return rv 
            

• 执行用时：1428 ms, 在所有 Python3 提交中击败了89.12%的用户
• 内存消耗：19.3 MB, 在所有 Python3 提交中击败了100.00%的用户

• failed try

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        count = 0 
        for i in range(len(nums) - 1):
            for j in range(i, len(nums)):
                if nums[i] > nums[j]:
                    count += 1
        return count