Day3 25/2/16 SUN

【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵）】https://www.bilibili.com/video/BV13g41157hK?p=4&vd_source=04ee94ad3f2168d7d5252c857a2bf358

目录

2、认识O(NlogN)的排序

2.2 归并排序

2.2.1 思路&代码实现

2.2.2 时间复杂度

2.2.3 应用

2.2.3.1 小和问题

2.2.3.2 逆序对问题

---

笔记：

2、认识O(NlogN)的排序

2.2 归并排序

2.2.1 思路&代码实现

在新数组newArr[]开辟存储空间，大小为R-L+1，也就是原始数组的元素个数。

左数组的范围arr[L]到arr[M]，右数组的范围arr[M+1]到arr[R]，两个指针的范围小于等于各自组的右边界（p1<=M，p2<=R）。

当p1<p2，将p1指向的数拷贝到newArr[i]中，然后指针和i都++；当p2<p1，则对p2进行相同操作；当p1=p2，先拷贝p1再拷贝p2，然后p1++、p2++、i=i+2

当p1先到达右边界，则将p2往后的内容都拷贝到newArr[]中：newArr[i++] = arr[p2++];当p2先达右边界：newArr[i++] = arr[p1++];

整体代码：

public static void mergeSort(int[] arr, int L, int M, int R){int[] newArr = new int[R-L+1];int i=0;int p1=L, p2=M+1;while( p1<=M && p2 <=R ){newArr[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; //这部分等效于if( arr[p1] <= arr[p2] ){ newArr[i++]=arr[p1++]}else{newArr[i++]=arr[p2++]}}//处理其中一个指针到达边界的情况while ( p1 <= M ){newArr[i++] = arr[p1++]}while ( p2 <= R ){newArr[i++] = arr[p2++]}//如果要将排序后的新结果newArr替换掉旧数组arr，则可以用for循环逐个替换：for( i=0; i<arr.length; i++){arr[L+i] = newArr[i];}}

2.2.2 时间复杂度

如果用master公式计算这个归并排序代码的时间复杂度：T(N) = 2*T(N/2) + O(N)

解释：左数组和右数组的数据量都是N/2，且都是先组内排序再利用双指针遍历后放入数组（遍历操作的时间复杂度是O(N)）。

归并排序的时间复杂度O(NlogN)优于选择排序、插入排序等O(N…^2)的原因：

在选择排序、插入排序中，遍历一遍含n个元素的数组只能确定下来一个元素的位置，其余的比较被浪费了。

而在归并排序中，两个子数组的元素都是有序的，因此每一次比较都能确定一个元素的位置并使指针后移，继续比较后续的元素。

2.2.3 应用

2.2.3.1 小和问题

小和问题：一个数组中，遍历每个元素然后把左侧比当前数小的数累加起来，得到这个数组的小和。

举例数组元素为1、3、4、2、5的例子。

遍历开始前，小和sum=0；

遍历到1，左侧无更小值，sum=0；

遍历到3，左侧有1比3小，sum=sum+1；

遍历到4，左侧有1、3比4小，sum=sum+1+3；

遍历到2，左侧有1比2小，sum=sum+1；

遍历到5，左侧有1、3、4、2比5小，sum=sum+1+3+4+2；

此情景中的最终小和为16。

计算小和有2种时间复杂度不同的方法。

方法1：O(N^2)。使用最纯粹的遍历方法。遍历数组然后将当前元素和左侧元素逐个比较、加和，得到小和。

方法2：O(NlogN)。使用了归并排序，对于每个元素，如果它的右侧有m个元素比它大，则再加上m*当前元素的值。

方法1不涉及给元素排序，因此要想得到某个元素在数组中的小和，必须遍历一遍数组才能得到。对于含N个元素的数组，得到每个元素的小和都需要遍历一遍N个元素，因此时间复杂度是N^2。

而方法2的归并排序则涉及给元素按大小排序，找到当前元素的插入位置的时候，它右侧的元素必然大于它。边比较数字大小边排好序，省去了元素元素和必然大于它的元素的比较。但仍需要遍历一遍N个元素，所以时间复杂度是N*logN。

举例来讲，数组为1、5、3、2、4、5。使用归并排序方法计算到2的小和时，前面已经计算完小和的1、5、3在newArr[]中被按升序排列为1、3、5，然后2和3比较后就无需再比较2和5，省去了部分操作。正是这部分操作使arr[]中的元素无需再和远比它大的元素进行比较，使时间复杂度从O(N^2)提升为了O(NlogN)。空间复杂度从O(1)降为了O(N)。

2.2.3.2 逆序对问题

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

小和的反向版本。小和是从左侧找比当前元素小的，逆序对是从右侧找比当前元素小的。

我的代码：

class Solution {int count;public int reversePairs(int[] record) {//先排序，再遍历比较，小于则逆序对数量++this.count = 0;merge(record, 0, record.length-1);return count;}private void merge(int[] arr, int L, int R){int M = (R+L)/2;if(L<R){merge(arr, L, M);        //左拆分merge(arr, M+1, R);      //右拆分mergeSort(arr, L, M, R); //合并}}private void mergeSort(int[] arr, int L, int M, int R){int[] temp = new int[R-L+1];int index = 0;int i=L, j=M+1;while(i<=M && j<=R){    //也就是两组的index都不越界的情况下if(arr[i] <= arr[j])temp[index++]=arr[i++]; //非逆序的情况else{count += (M-i+1);   //有多少个数小于当前的数temp[index++] = arr[j++];}}//把左边剩余的数移入数组while (i <= M) {temp[index++] = arr[i++];}//把右边剩余的数移入数组while (j <= R) {temp[index++] = arr[j++];}//把新数组中的数覆盖nums数组for (int k = 0; k < temp.length; k++) {arr[k + L] = temp[k];}}
}