归并延拓：LeetCode归并排序逆序对问题

🕗 发布于 2025-01-20 20:43 leetcode 算法归并排序

前言

欢迎来到我的算法探索博客，在这里，我将通过解析精选的LeetCode题目，与您分享深刻的解题思路、多元化的解决方案以及宝贵的实战经验，旨在帮助每一位读者提升编程技能，领略算法之美。
👉更多高频有趣LeetCode算法题

归并排序（Merge Sort） 是一种经典的分治算法，核心思想是将一个数组分解成更小的子数组，然后再将这些子数组合并成有序的数组。归并排序的步骤如下：

分解：将待排序的数组不断分割，直到每个子数组只有一个元素。
合并：从两个已排序的子数组开始，逐一比较元素并将它们合并成一个新的有序数组。

归并排序的时间复杂度为 𝑂(𝑛log(𝑛))，它是一种稳定的排序算法，适用于大规模数据的排序。由于其分治的特性，它的空间复杂度为 𝑂(𝑛)，需要额外的存储空间。

虽然归并排序的初衷是排序，但它在处理与排序相关的其他问题时也非常有用。

⚠️注意：归并排序具体实现原理及代码本篇文章不做讲解，默认阅读者已经掌握归并排序并能熟练默写代码。一定要有排序算法基础才能继续往下哦！ 归并排序具体实现原理请看：👉这里

原理：归并排序

本篇文章不做详细讲解。
归并排序具体实现原理请看：👉这里

实战：经典例题讲解

LCR 170.交易逆序对的总数

🌵题目描述

在这里插入图片描述

🌼核心思路

其实刚拿到这个题呢，最容易想到的是暴力解法：两层for循环。

使用两层 for 循环枚举所有的数对，逐一判断是否构成逆序关系。

public class Solution {
    public int reversePairs(int[] nums) {
        int res = 0;
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] > nums[j]) {
                    res++;
                }
            }
        }
        return res;
    }
}

提交代码发现超时，如果就这么简单做完也不可能打上困难的标签了😅

接下来看一下比较优雅的做法 （当然也可以用树状数组解决逆序数问题，本篇文章不做讲解）：

利用归并排序来计算逆序对是一种经典且高效的做法，核心思想在于利用归并过程中的有序性来快速统计逆序对。在归并排序中，递归地将数组分为左右两部分，而在合并这两部分时，我们可以通过比较元素的大小来判断逆序对的数量。

具体而言，逆序对的计算可以分为三个部分：

左侧区间内的逆序对。
右侧区间内的逆序对。
横跨左右区间的逆序对。

在分割过程中不做任何操作，而是在合并阶段，通过数组的部分有序性，我们能够迅速计算出跨区间的逆序对。尤其是在合并过程中，每当一个左侧元素大于右侧元素时，就能够确定这个左侧元素与右侧区间中剩下的所有元素构成逆序对。因此，排序的过程非常关键，因为只有通过排序，才能利用元素之间的顺序关系有效地计算逆序对，并避免重复计算。

所以就会有两种写法了：

1、计算第1个子区间右侧有多少个数比他小，计算逆序对的个数；
2、计算第2个子区间左侧有多少个数比他大，计算逆序对的个数。

在这里插入图片描述

注意：两者不能同时计算，否则会计算重复。

🌿代码实现

Java

第一版：计算右侧有多少个数比他小

class Solution {
    int[] record, temp;

    public int reversePairs(int[] record) {
        int n = record.length;
        temp = new int[n];
        if (n < 2)
            return 0;
        return reversePairs(record, 0, n - 1, temp);
    }

    public int reversePairs(int[] record, int left, int right, int[] temp) {
        if (left >= right)
            return 0;
        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(record, left, mid, temp);
        int rightPairs = reversePairs(record, mid + 1, right, temp);

        // 小优化
        if (record[mid] < record[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int mergePairs = merge(record, left, mid, right, temp);
        return leftPairs + rightPairs + mergePairs;
    }

    private int merge(int[] a, int left, int mid, int right, int[] temp) {
        // 定义三个指针
        int p1 = left;
        int p2 = mid + 1;
        int p3 = 0; // 记录辅助数组中的索引
        int res = 0;

        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2]) {
                temp[p3++] = a[p1++];
                res += p2 - (mid + 1);
            } else {
                temp[p3++] = a[p2++];

            }
        }

        // 将左边剩余的数据填充到辅助数组中
        while (p1 <= mid) {
            temp[p3++] = a[p1++];
            // 此时p2 = right + 1 所以（right + 1） - （mid + 1）
            res += right - mid;
        }

        // 将右边剩余的数据填充到辅助数组中
        while (p2 <= right) {
            temp[p3++] = a[p2++];
        }

        // 把临时数组中的数据拷贝到原数组中
        int t = 0;
        while (left <= right) {
            a[left++] = temp[t++];
        }

        return res;
    }
}

第二版：计算左侧有多少个数比他大

class Solution {
    int[] record, temp;

    public int reversePairs(int[] record) {
        int n = record.length;
        temp = new int[n];
        if (n < 2)
            return 0;
        return reversePairs(record, 0, n - 1, temp);
    }

    public int reversePairs(int[] record, int left, int right, int[] temp) {
        if (left >= right)
            return 0;
        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(record, left, mid, temp);
        int rightPairs = reversePairs(record, mid + 1, right, temp);

        // 小优化
        if (record[mid] < record[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int mergePairs = merge(record, left, mid, right, temp);
        return leftPairs + rightPairs + mergePairs;
    }

    private int merge(int[] a, int left, int mid, int right, int[] temp) {
        // 定义三个指针
        int p1 = left;
        int p2 = mid + 1;
        int p3 = 0; // 记录辅助数组中的索引
        int res = 0;

        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2]) {
                temp[p3++] = a[p1++];
            } else {
                temp[p3++] = a[p2++];
                res += mid + 1 - p1;
            }
        }

        // 将左边剩余的数据填充到辅助数组中
        while (p1 <= mid) {
            temp[p3++] = a[p1++];
        }

        // 将右边剩余的数据填充到辅助数组中
        while (p2 <= right) {
            temp[p3++] = a[p2++];
            // 此时p1 = mid + 1 所以也可以不写res
            // res += mid + 1 - p1;
        }

        // 把临时数组中的数据拷贝到原数组中
        int t = 0;
        while (left <= right) {
            a[left++] = temp[t++];
        }

        return res;
    }
}

Python

第一版：计算右侧有多少个数比他小

class Solution(object):
    def reversePairs(self, record):
        n = len(record)
        temp = [0] * n
        if n < 2:
            return 0
        return self.reversePairsHelper(record, 0, n - 1, temp)

    def reversePairsHelper(self, record, left, right, temp):
        if left >= right:
            return 0
        mid = left + (right - left) // 2
        leftPairs = self.reversePairsHelper(record, left, mid, temp)
        rightPairs = self.reversePairsHelper(record, mid + 1, right, temp)

        # 小优化
        if record[mid] < record[mid + 1]:
            return leftPairs + rightPairs

        mergePairs = self.merge(record, left, mid, right, temp)
        return leftPairs + rightPairs + mergePairs

    def merge(self, record, left, mid, right, temp):
        p1 = left
        p2 = mid + 1
        p3 = 0
        res = 0

        while p1 <= mid and p2 <= right:
            if record[p1] <= record[p2]:
                temp[p3] = record[p1]
                p3 += 1
                p1 += 1
                res += p2 - (mid + 1)
            else:
                temp[p3] = record[p2]
                p3 += 1
                p2 += 1

        while p1 <= mid:
            temp[p3] = record[p1]
            p3 += 1
            p1 += 1
            res += right - mid

        while p2 <= right:
            temp[p3] = record[p2]
            p3 += 1
            p2 += 1

        t = 0
        while left <= right:
            record[left] = temp[t]
            left += 1
            t += 1

        return res

C++

第一版：计算右侧有多少个数比他小

class Solution {
public:
    int reversePairs(vector<int>& record) {
        int n = record.size();
        vector<int> temp(n);
        if (n < 2)
            return 0;
        return reversePairsHelper(record, 0, n - 1, temp);
    }

private:
    int reversePairsHelper(vector<int>& record, int left, int right, vector<int>& temp) {
        if (left >= right)
            return 0;
        int mid = left + (right - left) / 2;
        int leftPairs = reversePairsHelper(record, left, mid, temp);
        int rightPairs = reversePairsHelper(record, mid + 1, right, temp);

        // 小优化
        if (record[mid] < record[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int mergePairs = merge(record, left, mid, right, temp);
        return leftPairs + rightPairs + mergePairs;
    }

    int merge(vector<int>& record, int left, int mid, int right, vector<int>& temp) {
        int p1 = left;
        int p2 = mid + 1;
        int p3 = 0;
        int res = 0;

        while (p1 <= mid && p2 <= right) {
            if (record[p1] <= record[p2]) {
                temp[p3++] = record[p1++];
                res += p2 - (mid + 1);
            } else {
                temp[p3++] = record[p2++];
            }
        }

        while (p1 <= mid) {
            temp[p3++] = record[p1++];
            res += right - mid;
        }

        while (p2 <= right) {
            temp[p3++] = record[p2++];
        }

        int t = 0;
        while (left <= right) {
            record[left++] = temp[t++];
        }

        return res;
    }
};

结语

如果您渴望探索更多精心挑选的高频LeetCode面试题，以及它们背后的巧妙解法，欢迎您访问我的博客，那里有我精心准备的一系列文章，旨在帮助技术爱好者们提升算法能力与编程技巧。

👉更多高频有趣LeetCode算法题

在我的博客中，每一篇文章都是我对算法世界的一次深入挖掘，不仅包含详尽的题目解析，还有我个人的心得体会、优化思路及实战经验分享。无论是准备面试还是追求技术成长，我相信这些内容都能为您提供宝贵的参考与启发。期待您的光临，让我们共同在技术之路上不断前行！

原文地址：https://blog.csdn.net/weixin_74199893/article/details/145238863

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Linux中的基本指令（一）
下一篇：国产编辑器EverEdit - 合并行

Redis和MongoDB的区别
在项目选型阶段，MongoDB被选中主要是基于其处理大规模数据集的能力，而当时并未深入探讨其他替代方案。此前，Redis被用于管理少量但访问频繁的热数据。目前，项目采用MongoDB存储百万级数据，预
阅读更多2025-01-20
MySQL数据库入门到大蛇尚硅谷宋红康老师笔记基础篇 part 5
可以使用不在SELECT列表中的列排序。在对多列进行排序的时候，首先排序的第一列必须有相同的列值，才会对第二列进行排序。如果第一列数据中所有值都是唯一的，将不再对第二列进行排序。
阅读更多2025-01-20
HarmonyOS NEXT开发进阶（十）：UIAbility 组件交互
UIAbility是系统调度的最小单元。在设备内的功能模块之间跳转时，会涉及到启动特定的UIAbility，该UIAbility可以是应用内的其他UIAbility，也可以是其他应用的UIAbilit
阅读更多2025-01-20
SAP+AI 的常见应用场景
SAP结合AI技术的应用场景非常广泛，涵盖了企业运营的多个关键领域。
阅读更多2025-01-20
力扣动态规划-4【算法学习day.98】
##我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力
阅读更多2025-01-20
[STM32 HAL库]串口中断编程思路
很多情况下，需要串口进行接收数据，并且要对接收的数据进行处理。这篇文章分析了两种数据处理的方法，一个是在回调函数里直接处理数据，另一个在回调函数中设置标志位，在主函数里读取标志位再进行数据处理。两种方
阅读更多2025-01-20
《CPython Internals》阅读笔记：p232-p249
无。overhead的字面意思是：abovethehead,后来演变成"representthingssituatedaboveormetaphoricallyreferringtoaddi
阅读更多2025-01-20
CT重建笔记（三）——共轭梯度法
Axb其中，A为大型稀疏矩阵。利用系统矩阵的稀疏性可以把原问题缩减为一个小问题，从而加速求解。对于同样维度的问题，采用缩减法对于线性方程组问题不如特征值问题的效率提高明显。我的毕业论文就是研究有限元模
阅读更多2025-01-20
如何保证调用小红书的笔记详情API的安全性？
遵循官方安全规定与协议认证和授权管理网络安全防护数据安全处理安全监控与应急响应
阅读更多2025-01-20
Windows电脑安装File Browser与cpolar轻松搭建本地云盘
无论是个人用户还是企业团队，都希望能够有一个高效、安全的解决方案来管理自己的文件和文档。而传统的云存储服务虽然方便，但往往伴随着高昂的成本和服务提供商的数据隐私问题。本文将详细介绍如何在Windows
阅读更多2025-01-20

归并延拓：LeetCode归并排序逆序对问题

前言

原理：归并排序

实战：经典例题讲解

LCR 170.交易逆序对的总数

🌵题目描述

🌼核心思路

🌿代码实现

Java

Python

C++

结语

相关文章