归并延拓：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. 左侧区间内的逆序对。
2. 右侧区间内的逆序对。
3. 横跨左右区间的逆序对。

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

所以就会有两种写法了：

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] * nif n < 2:return 0return self.reversePairsHelper(record, 0, n - 1, temp)def reversePairsHelper(self, record, left, right, temp):if left >= right:return 0mid = left + (right - left) // 2leftPairs = self.reversePairsHelper(record, left, mid, temp)rightPairs = self.reversePairsHelper(record, mid + 1, right, temp)# 小优化if record[mid] < record[mid + 1]:return leftPairs + rightPairsmergePairs = self.merge(record, left, mid, right, temp)return leftPairs + rightPairs + mergePairsdef merge(self, record, left, mid, right, temp):p1 = leftp2 = mid + 1p3 = 0res = 0while p1 <= mid and p2 <= right:if record[p1] <= record[p2]:temp[p3] = record[p1]p3 += 1p1 += 1res += p2 - (mid + 1)else:temp[p3] = record[p2]p3 += 1p2 += 1while p1 <= mid:temp[p3] = record[p1]p3 += 1p1 += 1res += right - midwhile p2 <= right:temp[p3] = record[p2]p3 += 1p2 += 1t = 0while left <= right:record[left] = temp[t]left += 1t += 1return 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算法题

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