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

系统管理员 2024-03-16 18:36 45阅读 0赞

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

*  前言
 *  一、暴力求解
 *  二、归并排序后再求解

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

## 前言 ##

**在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。**  
![在这里插入图片描述][42687a4a0f3d42d089cc734eac661f18.png]

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

## 一、暴力求解 ##

暴力求解依然可以用来解这道题目，但是问题在于会超时，因为时间复杂度过大

public int reversePairs(int[] nums) {
        
            int cnt = 0;
            int len = nums.length;
            for (int i = 0; i < len - 1; i++) {
        
                for (int j = i + 1; j < len; j++) {
        
                    if (nums[i] > nums[j]) {
        
                        cnt++;
                    }
                }
            }
            return cnt;
        }

![在这里插入图片描述][a57411d271934059a8888257aa9f6c43.png]

## 二、归并排序后再求解 ##

**图片和部分内容来自：**  
[剑指 Offer 51. 数组中的逆序对（归并排序，清晰图解）][Offer 51.]  
[暴力解法、分治思想、树状数组][Link 1]

**分： 不断将数组从中点位置划分开（即二分法），将整个数组的排序问题转化为子数组的排序问题；**

**治： 划分到子数组长度为 1 时，开始向上合并，不断将 较短排序数组 合并为 较长排序数组，直至合并至原数组时完成排序；**

**合并阶段 本质上是 合并两个排序数组 的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」**

int cnt = 0;//需要不断累加，因此不能是局部变量，应该是个全局都可以使用的变量
    
        public int reversePairs(int[] nums) {
        
            mergeSort(nums,0,nums.length - 1,cnt);
            return cnt;
        }
    
        public void mergeSort(int[] nums, int left, int right, int cnt){
        
            if(left >= right){
        
                return ;
            }
            int mid = (right - left)/2 + left;
            mergeSort(nums, left, mid, cnt);
            mergeSort(nums, mid + 1, right, cnt);
            merge(nums, left, mid, right);
        }
    
        public void merge(int[] nums, int left, int mid, int right){
        
            int temp[] = new int[right - left + 1];
            int i = left;
            int j = mid + 1;
            int k = 0;
            while(i <= mid && j <= right){
        
                if(nums[i] > nums[j]){
        
                    cnt = cnt + mid - i + 1;
                    temp[k] = nums[j];
                    k++;
                    j++;
                }else{
        
                    temp[k] = nums[i];
                    k++;
                    i++;
                }
            }
            while(i <= mid){
        
                temp[k] = nums[i];
                i++;
                k++;
            }
            while(j <= right){
        
                temp[k] = nums[j];
                j++;
                k++;
            }
            for(int m = 0; m < right - left + 1; m++){
        
                nums[m + left] = temp[m];
            }
        }

![在这里插入图片描述][0bcd64d8be4d48a0a96ce916b05bd3d7.png]  
![在这里插入图片描述][55f903423dd94cf9af5978c25225a466.png]

[42687a4a0f3d42d089cc734eac661f18.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/69617dce53c84dd29fb89a08b264894c.png
[a57411d271934059a8888257aa9f6c43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/cedcfd742da142cdb368981ca47442f3.png
[Offer 51.]: https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/622496/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
[Link 1]: https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/92471/bao-li-jie-fa-fen-zhi-si-xiang-shu-zhuang-shu-zu-b/
[0bcd64d8be4d48a0a96ce916b05bd3d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2b568453b04945c7a255890dd8206923.png
[55f903423dd94cf9af5978c25225a466.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b8261e8558d24a749fe775af5095d1e2.png