剑指 Offer 51. 数组中的逆序对

ゝ一世哀愁。 2022-12-31 04:23 158阅读 0赞

故心故心故心故心小故冲啊

--------------------

### 文章目录 ###

*  题目:在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 *  解法一:双for暴力解法(超出时间限制)
 *  解法二:归并排序（正确解法）

--------------------

# 题目:在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 #

示例 1:  
输入: \[7,5,6,4\]  
输出: 5

# 解法一:双for暴力解法(超出时间限制) #

//计数
         var count = 0;
         //双for循环(暴力解法)
         for(var i =0;i<nums.length;i++){ 
             for(var j = i+1;j<nums.length;j++){ 
                 if(nums[i]>nums[j]){ 
                     count++;
                 }
             }
         }
         return count;

# 解法二:归并排序（正确解法） #

在归并中并排序好了

*/
    var reversePairs = function(nums) { 
      let result = 0
        //归并排序
         function mergeSort(arr){ 
            if(arr.length < 2) return arr
            let len = arr.length
            let mid = Math.floor(len/2)
            return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
        }
        function merge(left, right){ 
            let res = []
            //直到长度为0时 ,才不会去比较
            while(left.length && right.length){ 
            //在排序好的左右数组中,若是左边第一个大于右边第一个
                if(left[0] <= right[0]){ 
                //删除左边第一个
                    res.push(left.shift())
                }else{ 
                    //若是小于
                    //逆数组数量加+1,并删除右边第一个
                    result += left.length
                    res.push(right.shift())
                }
            }
            return res.concat(left, right)
        }
        mergeSort(nums)
        return result
    }