翻转对

不念不忘少年蓝@ 2022-12-24 12:55 96阅读 0赞

> leetcode 493题 \[hard\]  
> 中：[翻转对][Link 1]  
> 英：[Reverse Pairs][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解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;
        };

[Link 1]: https://leetcode-cn.com/problems/reverse-pairs/
[Reverse Pairs]: https://leetcode.com/problems/reverse-pairs/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/bb457d412df246cd9237d38652bda505.png