3d网站设计,家装室内设计培训班哪里,东莞网站建设基本流程,软件培训记录前言 欢迎来到我的算法探索博客#xff0c;在这里#xff0c;我将通过解析精选的LeetCode题目#xff0c;与您分享深刻的解题思路、多元化的解决方案以及宝贵的实战经验#xff0c;旨在帮助每一位读者提升编程技能#xff0c;领略算法之美。 #x1f449;更多高频有趣Lee…前言 欢迎来到我的算法探索博客在这里我将通过解析精选的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 1res 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 resC
第一版计算右侧有多少个数比他小
class Solution {
public:int reversePairs(vectorint record) {int n record.size();vectorint temp(n);if (n 2)return 0;return reversePairsHelper(record, 0, n - 1, temp);}private:int reversePairsHelper(vectorint record, int left, int right, vectorint 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(vectorint record, int left, int mid, int right, vectorint 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算法题
在我的博客中每一篇文章都是我对算法世界的一次深入挖掘不仅包含详尽的题目解析还有我个人的心得体会、优化思路及实战经验分享。无论是准备面试还是追求技术成长我相信这些内容都能为您提供宝贵的参考与启发。期待您的光临让我们共同在技术之路上不断前行
