无锡网站开发公司电话,免费网店代运营,wordpress内存溢出,企业头像logo设计一、基本思路
我们以一个归并排序为例。
. - 力扣#xff08;LeetCode#xff09; 归并排序的思想#xff1a;得到两个有序数组#xff0c;把两个有序数组合并#xff0c;传到下一层递归#xff0c;一直得到两个有序数组#xff0c;一直合并#xff0c;最后就能得到有…一、基本思路
我们以一个归并排序为例。
. - 力扣LeetCode 归并排序的思想得到两个有序数组把两个有序数组合并传到下一层递归一直得到两个有序数组一直合并最后就能得到有序数组。
那其实有许多问题需要解释
1、如何得到两个有序数组一开始可都是乱序啊
一个数组一直被一分为二最后是不是就会被分成一个数组里面就一个元素一个元素不就有序了。
那么一旦我们有了两个有序数组合并两个有序数组之后的大有序数组随递归传到上一层是不是就作为了一个有序数组和另外一层递归上来的有序数组就可以再次合并直到递归结束数组就被排序完成了。
2、如何理解在函数最开始写上“mergeSort(left, mid, nums); mergeSort(mid 1, right, nums);” 就可以认为接下来是排好序的两个有序数组呢
因为在这两个语句之前所有的递归都是在做mergeSort(left, mid, nums); mergeSort(mid 1, right, nums);这两个语句的左右数组排序传递到这一层的递归就是左右有序的两个数组。
所以我认为的归并排序本质就是把一个数组在中间劈开然后交给下一层递归一直把一段数组一分为二直到一个数组里面只有一个这时满足两个数组有序开始回溯合并两个有序数组后向上交付数组。
二、例题
1、逆序对
. - 力扣LeetCode 思路我们得到一个数组以mid为中心在左边挑一下逆序对个数不就是把左边看成一个数组得到递归的结果在右边挑一下逆序对个数最后得到两个有序数组之后用一下两种方式调一下左右数组里面的逆序对。 但是上面代码中我递增归并一开始写成了 ans cur2 - mid - 1其实这是错的错因是我在要cur2移动的情况下用右边的数组来统计逆序对个数是错的因为没有判断左边的情况所以这种题如果移动cur1就要以右边数组作为基准移动cur2要以左边数组作为基准。
2、翻转对
. - 力扣LeetCode 思路和上一题非常类似但是注意由于不是11的关系不能把计算结果的过程和排序混在一起必须先是计算结果再排序。
3、计算右侧小的元素个数
. - 力扣LeetCode 思路和逆序对思路一样只不过要注意由于是返回数组我们必须记录原来数组中的值与下标的对应关系但是请注意不能用哈希表记录因为原数组会有重复导致键值重复所以只能用index数组对应值值移动index数组也移动。
