【算法100天 | 13】归并排序引出的系列问题（小和、逆序对、特定逆序对）

淡淡的烟草味﹌ 2023-09-24 12:41 57阅读 0赞

#### 文章目录 ####

*   *  1、数组的小和
     *   *  1）思路
         *  2）代码
     *  2、逆序对
     *   *  1）思路
         *  2）代码
     *  3、特定逆序对
     *   *  1）思路
         *  2）代码

### 1、数组的小和 ###

**什么是小和？**

设 array为一个有n个数字的数组(n>1)。如果存在正整数 i，j，使得 0 ≤ i ≤ j ≤ n-1 且 array\[i\] < array\[j\]，则针对数组中每个位置的 j，所有满足条件的i位置的数字 之和为j位置的小和，所有j位置的小和 累加则为数组的小和。

**例如：数组(3,1,4,5,2)的小和组成：**

1.  对于数字3：没有小和
2.  对于数字1：没有小和
3.  对于数字4，小和为：3 + 1 = 4；
4.  对于数字5，小和为：3 + 1 + 4 = 8；
5.  对于数组2，小和为：1；
6.  **所以对于整个数组，小和为：0 + 0+ 4 + 8 + 1 = 13；**

#### 1）思路 ####

先找出每个数字num的右边有多少个数（count）比它大，则数组的小和可以表示为 数组中每个数字的（num \* count）累加之和。

暴力解法的时间复杂度为O(n^2)，而在归并排序的过程中找到，时间复杂度仅为O(nlogn)，因此在归并排序的过程去找到所有的小和。

#### 2）代码 ####

public static int smallSum(int[] arr) {
        
        if (arr == null || arr.length < 2) {
        
            return 0;
        }
        int n = arr.length;
        int[] temp = new int[n];
    
        return sort(arr, 0, n - 1, temp);
    }
    
    private static int sort(int[] arr, int left, int right, int[] temp) {
        
        if (left >= right) {
        
            return 0;
        }
        int mid = left + (right - left) / 2;
        return sort(arr, left, mid, temp)
                + sort(arr, mid + 1, right, temp)
                + merge(arr, left, mid, right, temp);
    }
    
    private static int merge(int[] arr, int left, int mid, int right, int[] temp) {
        
        int pLeft = left;
        int pRight = mid + 1;
        int t = 0;
        // 小和
        int res = 0;
        while (pLeft <= mid && pRight <= right) {
        
            // 找出右序列中比左序列中某个数字大的数字个数count，res累加arr[pLeft] * count
            res += arr[pLeft] < arr[pRight] ? (right - pRight + 1) * arr[pLeft] : 0;
            temp[t++] = arr[pLeft] <= arr[pRight] ? arr[pLeft++] : arr[pRight++];
        }
        while (pLeft <= mid) {
        
            temp[t++] = arr[pLeft++];
        }
        while (pRight <= right) {
        
            temp[t++] = arr[pRight++];
        }
    
        t = 0;
        while (left <= right) {
        
            arr[left++] = temp[t++];
        }
        return res;
    }

### 2、逆序对 ###

**什么是逆序对？**

设 array为一个有n个数字的数组(n>1)。如果存在正整数i，j使得 0 ≤ i < j≤ n-1 且 array\[i\] > array\[j\]。则<array\[i\],array\[j\]>这两个数 称为array的一个逆序对，也称作逆序数。

例如：数组(3,1,4,5,2)的逆序对有(3,1)，(3,2)，(4,2)，(5,2)；一共4个逆序对。

简言之，**逆序对**就是数组中任意两个数满足大的在前,小的在后的组合。

#### 1）思路 ####

在归并排序的过程中，每次都会将左序列 和 右序列中的数对比，只需要在每次对比时 统计左序列中的某个数字 比 右序列中几个数字大，将数字个数累加到结果上即可。

整体时间复杂度只为O(nlogn)，而暴力解法的时间复杂度为O(n^2)。

#### 2）代码 ####

public static int reversePairs(int[] arr) {
        
        if (arr == null || arr.length < 2) {
        
            return 0;
        }
        int n = arr.length;
        int[] temp = new int[n];
    
        return sort(arr, 0, n - 1, temp);
    }
    
    private static int sort(int[] arr, int left, int right, int[] temp) {
        
        if (left >= right) {
        
            return 0;
        }
        int mid = left + (right - left) / 2;
        return sort(arr, left, mid, temp)
                + sort(arr, mid + 1, right, temp)
                + merge(arr, left, mid, right, temp);
    }
    
    private static int merge(int[] arr, int left, int mid, int right, int[] temp) {
        
        int pLeft = mid;
        int pRight = right;
        int t = 0;
        // 逆序对个数
        int res = 0;
        while (pLeft >= left && pRight >= mid + 1) {
        
            // 找出左序列的数 比 右序列中的几个数大
            res += arr[pLeft] > arr[pRight] ? (pRight - mid) : 0;
            temp[t++] = arr[pLeft] > arr[pRight] ? arr[pLeft--] : arr[pRight--];
        }
        while (pLeft >= left) {
        
            temp[t++] = arr[pLeft--];
        }
        while (pRight >= mid + 1) {
        
            temp[t++] = arr[pRight--];
        }
    
        t = 0;
        while (right >= left) {
        
            arr[right--] = temp[t++];
        }
        return res;
    }

### 3、特定逆序对 ###

**什么是特定逆序对？**

数组中每个位置的数字num 的右边数(rightNum) \* 2 < num 的数字 个数之和。这里的2 可以是任意数。

**例如：数组(3, 1, 13, 19, 7, 2, 5)的特定逆序对组成：**

1.  对于数字3：特定逆序对为：(3,1)
2.  对于数字1：没有特定逆序对
3.  对于数字13，特定逆序对为：(13,2)，(13,5)
4.  对于数字19，特定逆序对为：(19,7)，(19,2)，(19,5)
5.  对于数字7，特定逆序对为：(7,2)
6.  对于数字2，没有特定逆序对
7.  对于数字5，没有特定逆序对
8.  **所以对于整个数组，特定逆序对有：(3,1)，(13,2)，(13,5)，(19,7)，(19,2)，(19,5)，(7,2)；一共7个。**

#### 1）思路 ####

在归并排序的过程中，每次都会将左序列 和 右序列中的数对比，只需要在每次对比时 统计左序列中的某个数字 比 右序列中几个数字 \* 2大，将数字个数累加到结果上即可。

整体时间复杂度只为O(nlogn)，而暴力解法的时间复杂度为O(n^2)。

#### 2）代码 ####

public static int reversePairs(int[] arr) {
        
        if (arr == null || arr.length < 2) {
        
            return 0;
        }
        int n = arr.length;
        int[] temp = new int[n];
    
        return sort(arr, 0, n - 1, temp);
    }
    
    private static int sort(int[] arr, int left, int right, int[] temp) {
        
        if (left >= right) {
        
            return 0;
        }
        int mid = left + (right - left) / 2;
        return sort(arr, left, mid, temp)
                + sort(arr, mid + 1, right, temp)
                + merge(arr, left, mid, right, temp);
    }
    
    private static int merge(int[] arr, int left, int mid, int right, int[] temp) {
        
    
        int res = 0;
        // 符合条件的数集：[M+1, windowR)，windowR是到不了的数字
        int windowR = mid + 1;
        for ( int i = left; i <= mid; i ++) {
        
            // 因为左半边序列也是有序的，所以左序列中下一个数一定arr[windowR] * 2 大，所以不需要重置windowR
            while (windowR <= right && arr[i] > (arr[windowR] * 2)) {
        
                windowR ++;
            }
            res += windowR - mid - 1;
        }
    
        int pLeft = left;
        int pRight = mid + 1;
        int t = 0;
        while (pLeft <= mid && pRight <= right) {
        
            temp[t++] = arr[pLeft] <= arr[pRight] ? arr[pLeft++] : arr[pRight++];
        }
        while (pLeft <= mid) {
        
            temp[t++] = arr[pLeft++];
        }
        while (pRight <= right) {
        
            temp[t++] = arr[pRight++];
        }
    
        t = 0;
        while (left <= right) {
        
            arr[left++] = temp[t++];
        }
        return res;
    }