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

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

题目来源：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

题目

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

示例 1:

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

输出: 5

解题思路

思路：归并排序

归并排序使用了分治的思想，这个过程需要使用递归来实现。在分治算法递归实现中，每层递归会涉及三个步骤：

分解：将原问题分解为一系列子问题；
解决：递归求解各个子问题，若子问题足够小，直接求解；
合并：将子问题的结果合并为原问题。

在本题当中，

分解：假设区间为 [left, right]，令 mid = [(left + right) / 2]，将 [left, right] 分成 [left, mid] 和 [mid + 1, right]；
解决：使用递归排序两个子序列；
合并：将已经排好的子序列 [left, mid] 和 [mid + 1, right] 合并

题目中要求返回数组构成逆序对的总数。逆序对：即是前面的一个数字大于后面的数字，那么这两个数字可以构成一个逆序对。

具体思想参考代码。

代码实现

class Solution:

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

        n = len(nums)

        if n < 2:

            return 0

        # 辅助数组，用于归并

        temp = [0] * n

        return self.count_invs(nums, 0, n - 1, temp)

    def count_invs(self, nums, left, right, temp):

        if left == right:

            return 0

        mid = (left + right) // 2

        left_pairs = self.count_invs(nums, left, mid, temp)

        right_pairs = self.count_invs(nums, mid+1, right, temp)

        # 这里表示已经排序好，并且已经计算左右两部分未排序前的逆序对

        invs_pairs = left_pairs + right_pairs

        if nums[mid] < nums[mid + 1]:

            # 这个时候表示都是顺序排序，不用计算两个区间交叉的逆序对，直接返回

            return invs_pairs

        # 这里计算区间交叉的逆序对

        invs_cross_pairs = self.merge_count(nums, left, mid, right, temp)

        return invs_pairs + invs_cross_pairs

    def merge_count(self, nums, left, mid, right, temp):

        # 现在两个区间都是有序的

        # 合并计算此时区间交叉的逆序对个数

        # 复制原数组到辅助数组

        for i in range(left, right + 1):

            temp[i] = nums[i]

        p = left

        q = mid + 1

        ans = 0

        for i in range(left, right + 1):

            # 这里归并剩余的部分

            if p > mid:

                nums[i] = temp[q]

                q += 1

            elif q > right:

                nums[i] = temp[p]

                p += 1

            elif temp[p] <= temp[q]:

                # 这个时候，前面部分区间的元素出列

                # 因为 p 对应的元素，比 q 对应的元素小

                # 那么 p 对应的元素一定比 q 对应元素后面的元素都小

                # 所以这个时候不统计逆序对，p 往前移动

                nums[i] = temp[p]

                p += 1

            else:

                # 这种属于相反的情况

                # p 对应的元素比 q 对应的元素大，

                # 那么 p 对应的元素后面的元素一定更大

                # 所以，元素出列同时统计逆序对

                # 这个时候，数组位置 p 到该区间末尾有多少个元素就有多少个逆序对，即是 mid - p + 1

                nums[i] = temp[q]

                q += 1

                ans += (mid - p + 1)

        return ans

实现结果

以上就是使用归并排序的思想，解决《面试题51. 数组中的逆序对》问题的主要内容。

欢迎关注微信公众号《书所集录》

巴特西

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

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

题目

解题思路

代码实现

实现结果

最新文章

热门文章