欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-27 20:30:04
面试题51. 数组中的逆序对 题目来源: "https://leetcode cn.com/problems/shu zu zhong de ni xu dui lcof/" 题目 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的 ......

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


题目来源:

题目


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

示例 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

实现结果


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


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


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