面试题51. 数组中的逆序对

一时失言乱红尘 2023-05-21 08:46 16阅读 0赞

**题目描述：**

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

**示例 1:**

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

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

**解题思路1:**

这道题，看起来很简单，但是双循环是会超出时间限制的

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

**代码1：**

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

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

**解题思路2:**归并排序

来源于：[力扣][Link 1]

「归并排序」是分治思想的典型应用，它包含这样三个步骤：

*  分解： 待排序的区间为  \[ l , r \] \[l, r\] \[l,r\]，令  m = ⌊ l + r 2 ⌋ m = \\lfloor \\frac\{l + r\}\{2\} \\rfloor m=⌊2l\+r⌋，我们把  \[ l , r \] \[l, r\] \[l,r\] 分成  \[ l , m \] \[l, m\] \[l,m\]和  \[ m + 1 , r \] \[m + 1, r\] \[m\+1,r\]
 *  解决： 使用归并排序递归地排序两个子序列
 *  合并： 把两个已经排好序的子序列  \[ l , m \] \[l, m\] \[l,m\]和  \[ m + 1 , r \] \[m + 1, r\] \[m\+1,r\] 合并起来

在待排序序列长度为 1 的时候，递归开始「回升」，因为我们默认长度为 1的序列是排好序的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 3]

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

**代码2：**

class Solution:
        def mergeSort(self, nums, tmp, l, r):
            if l >= r:  return 0
    
            mid = (l + r) // 2
            inv_count = self.mergeSort(nums, tmp, l, mid) + self.mergeSort(nums, tmp, mid + 1, r)
            i, j, pos = l, mid + 1, l
            while i <= mid and j <= r:
                if nums[i] <= nums[j]:
                    tmp[pos] = nums[i]
                    i += 1
                    inv_count += (j - (mid + 1))
                else:
                    tmp[pos] = nums[j]
                    j += 1
                pos += 1
            for k in range(i, mid + 1):
                tmp[pos] = nums[k]
                inv_count += (j - (mid + 1))
                pos += 1
            for k in range(j, r + 1):
                tmp[pos] = nums[k]
                pos += 1
            nums[l:r+1] = tmp[l:r+1]
            return inv_count
    
        def reversePairs(self, nums):
            n = len(nums)
            tmp = [0] * n
            return self.mergeSort(nums, tmp, 0, n - 1)

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

**题目来源：**

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

[Link 1]: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230521/83a9138dd0184e5797cf099df957d72e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230521/14a91036701f4df8a296aefe3a7ea7bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230521/1d6d4df548e74a9680f8a69d7ad9091b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230521/3a1f515604584d3a8dbd2af81afed2d5.png
[https_leetcode-cn.com_problems_shu-zu-zhong-de-ni-xu-dui-lcof]: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof