怎样优化网站排名开通企业网站

当前位置： 首页 > news >正文

怎样优化网站排名,开通企业网站,网站备案组织机构代码,制作人是干什么的目录 1、题目介绍 2、解题思路 2.1、暴力破解法 2.2、归并排序思想 2.2.1、画图详细讲解 2.2.2、归并排序解决逆序对的代码实现 1、题目介绍 首先阅读题目可以得出要点#xff0c;即当前数大于后数时则当作一个【逆序对】#xff0c;而题目是要求在一个数组中计算一共存… 目录 1、题目介绍 2、解题思路 2.1、暴力破解法 2.2、归并排序思想 2.2.1、画图详细讲解 2.2.2、归并排序解决逆序对的代码实现 1、题目介绍 首先阅读题目可以得出要点即当前数大于后数时则当作一个【逆序对】而题目是要求在一个数组中计算一共存在多少个这样的逆序对并输出结果。  原题链接LCR 170. 交易逆序对的总数 - 力扣LeetCode ​ 2、解题思路 2.1、暴力破解法 看到这里的第一反应就是这不是很简单吗心想着这困难题也不过如此吧笑。 就是直接使用暴力破解法只需要两个for循环嵌套一个record[ i ]在原地另一个record[ j ]将后面所有遍历一遍只要比record[ i ]的小就将计算器count加1然后i再从头遍历知道找完所有最后返回计数器count即可于是便奋笔疾书写了起来。 ​ int reversePairs(int* record, int recordSize) {if (recordSize 0){return 0;}int count 0;int i 0, j 0;for (i 0; i recordSize - 1; i){for (j i 1; j recordSize; j){if (record[i] record[j]){count;}}}return count; } 当写完然后测试了简答数据无误然后自信满满地点击提交结果却直接被打脸。 ​ 看了报错结果才恍然大悟看题目时漏看了数组长度。 题目设置的数组长度最长可达 50000因此使用暴力破解法虽然非常简单但是时间复杂度也非常大为O(n^2)这肯定会超出时间限制的。因此需要使用一种时间复杂度较小的遍历。到了这里才终于理解了这道题为什么是困难题 2.2、归并排序思想 这里思考了一下只要能找到 一种时间复杂度低并且通过比较排序的算法在比较排序的过程中顺便进行记录这样的化就能够解决这个问题了。 于是归并排序便浮现在眼前归并排序的时间复杂度很低只有O(nlogn)并且也是通过比较的方式进行排序那么只需要在传统的归并排序算法中添加一些用于记录前者大于后者计算器即可。 简单回顾一下归并排序的知识 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用递归或者说是分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序它包含这样三个步骤 分解把长度为n的待排序序列分成两个长度为n/2的子序列。例如L代表头部M代表中点R代表尾部将[ LR ]分成[ LM ]和[  M1R ]。解决使用归并排序递归地排序两个子序列。合并将两个排序好的子序列[ LM ]和[  M1R ]合并成一个最终的排序序列。 在待排序序列长度为 1 的时候递归开始「回升」因为我们默认长度为 1 的序列是排好序的。简单来说就是当分到单个子序列只剩下一个数字时一个数字就是天然了有序即此时左侧和右侧都排好序了然后递归进行回升操作。 由于篇幅原因如果想要更加详细地了解有关归并排序的知识可以前往往期博客中阅读 【算法与数据结构】归并排序的代码实现详细图解以及master公式的讲解_Hacynn的博客-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133516177?spm1001.2014.3001.5501 2.2.1、画图详细讲解 假设我们通过归并排序的「回升」操作已经得到了两个已排序的子序列并等待合并这两个子序列假设为左子序列[ 8,15,17,22,35 ]和右子序列[ 9,12,15,30,38 ]。然后用malloc开辟辅助数组help并定义一个变量sum用于记录当前逆序对的个数。 一开始我们先用p1指向左子序列的头部p2指向右子序列的头部i指向help数组的头部。 此时开始比较p1和p2指向的值我们发现p1小于p2不符合逆序对的前者大于后者因此不做其他操作直接将值放入help数组 i 位置中并且分别进行p1和i使指向下一个元素。 重复p1和p2的比较操作发现此时p1大于p2此时记录逆序对的sum本应该自增1。 但是这里我们可以发现一个规律因为左子序列是有序的如果p1此时的数比p2大那就证明p1后面的数字也依然比p2大因此逆序对应该有M-p11即4个分别是(159)、(179)、(229)、(359)。 所以此时sum应该4并将p2所指的较小值存入help中。 i、p2 此时p1仍然大于p2再次使用M-p11计算出逆序对为4个分别是(15,12)、(17,12)、(22,12)、(35,12)。 此时 sum   sum4并将12存入help中。 ip2 注意特殊此时p1 p2该算法在等于时尤为关键当相等时应该将左侧p1的15放入help中并p1如果放的是右侧p2的15存入就会丢失一部分逆序对这个原理读者可以自己画图理解。 剩下的部分依然按照此规律进行操作最终算出该轮遍历的逆序对数sum。  2.2.2、归并排序解决逆序对的代码实现 int ExternalSort(int* arr, int L, int M, int R) {int* help (int*)malloc(sizeof(int) * (R - L 1));int p1 L;int p2 M 1;int sum 0;int i 0;while ((p1 M) (p2 R)){//p1 大于 p2 则计算出逆袭对个数并加入sum中p1小于p2时则给0即不操作sum arr[p1] arr[p2] ? (M - p1 1) : 0;//较小的数拷贝进help数组相等时拷贝p1指针的数help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}//当有一个子序列遍历完了则将另外一个子序列中剩余的数据全部放入help数组中while (p1 M) { help[i] arr[p1]; }while (p2 R) { help[i] arr[p2]; }//将辅助数组help中已经合并完成的数据传回给原数组arr的相应位置for (i 0; i (R - L 1); i){arr[L i] help[i];}free(help);help NULL;return sum; //返回本轮操作的sum值}int MergeSort(int* arr, int L, int R) {if (L R){return 0;}int mid L (R - L) / 2;return MergeSort(arr, L, mid) //对拆分的左子序列进行递归操作MergeSort(arr, mid 1, R) //对拆分的右子序列进行递归操作ExternalSort(arr, L, mid, R); //外部排序并计算出逆序对sum }int reversePairs(int* record, int recordSize) {int ret 0;if (recordSize 0) //对空数组进行判断{return 0;}ret MergeSort(record, 0, recordSize - 1);return ret; } 到这里关于本题的解题过程就结束了 。 如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力 如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力 如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力