题目链接：点击打开链接
题目大意：略
解题思路
如下图所示，为数组 [7, 3, 2, 6, 0, 1, 5, 4][7,3,2,6,0,1,5,4] 的归并排序与逆序对统计过程。
结论：逆序对的总数就是归并排序的比较的次数累计和
代码中加了 TODO 的是应对题目，去了的话，就是正儿八经的归并排序，推荐先理解归并排序的代码框架，再看注释~
相关企业
- 字节跳动
- 华为
- 腾讯
AC 代码
classSolution { int[] arr, tmp; intres=0; publicintreversePairs(int[] nums) { arr=nums; tmp=newint[nums.length]; mergeSort(0, nums.length-1); returnres; } privatevoidmergeSort(intl, intr) { if (l>=r) { return; } intm= (l+r)/2; mergeSort(l, m); mergeSort(m+1, r); mergeArr(l, m, r); } privatevoidmergeArr(intl, intm, intr) { intk=0, i=l, j=m+1; intcnt=0; // TODOwhile (i<=m&&j<=r) { if (arr[i] <=arr[j]) { tmp[k++] =arr[i++]; cnt++; // TODO } else { tmp[k++] =arr[j++]; res+=m-l+1-cnt; // TODO: 左组数据总数 - 已经放入数组的个人 == 剩下的个数, 也就是左边比右边大的数据个数 } } while (i<=m) tmp[k++] =arr[i++]; while (j<=r) tmp[k++] =arr[j++]; for (i=0; i<k; i++) arr[l+i] =tmp[i]; } }
