leetcode 493题 [hard]
中：翻转对
英：Reverse Pairs

题解1：归并法

1. 假设当前两个子序列都排好序且统计了翻转对数量，那么对这两个子序列合并只需要再统计 nums[i] 在左子序列，nums[j] 在右子序列的翻转对数即可。（递归归并思想）

2. 子序列排序的目的：优化翻转对的计算，具体可见代码注释

3. 时间复杂度：O(nlogn)
   （归并法分割开销 O(logn)）* [（子序列计算翻转对开销 O(n)）+ （子序列排序开销 O(n)）] => O(nlogn)

4. 空间复杂度：O(n) 归并数组

5. 实现

   /*** @param {number[]} nums* @return {number}*/
   var reversePairs = function(nums) {/*** 归并排序法 + 优化剪枝* 时间复杂度：O(nlogn)* 空间复杂度：O(n) 归并新数组*/// 预处理（无）let result = 0;		// 统计重要翻转对数// 归并排序法function notJustMergeSort(_nums){// 预处理if(_nums.length <= 1) return _nums;// 分割let mid = Math.floor(_nums.length/2);let left = notJustMergeSort(_nums.slice(0, mid));let right = notJustMergeSort(_nums.slice(mid));let lLen = left.length;let rLen = right.length;// 处理（+优化剪枝）let J = rLen - 1;       // 优化（left元素左移时，说明_nums[i]变小，所以_nums[j]只要以上一次的j开始进行左移即可）for(let i=lLen-1; i>=0; i--){let has = false;    // 优化（若这一轮没有在_nums[j]中找到满足_nums[i] > 2*_nums[j]的结果，下一轮_nums[i]左移又会变的更小，更加不可能满足条件，直接退出_nums[i]的循环）for(let j=J; j>=0; j--){if(left[i] > 2*right[j]) {result += (j+1);    // 优化（每一轮j左移都会使得_nums[j]变小，当前满足 _nums[i] > 2*_nums[j]，后续的j必然也满足，可以提前结束判断）J = j;has = true;break;}}if(!has) break;}// 合并let lP = rP = 0;let mergeArr = [];while(true){if(lP >= lLen){mergeArr.push(...right.slice(rP));break;}else if(rP >= rLen){mergeArr.push(...left.slice(lP));break;}if(left[lP] <= right[rP]) mergeArr.push(left[lP++]);else mergeArr.push(right[rP++]);}return mergeArr;}notJustMergeSort(nums);return result;
   };