求数组arr中的降序对有多少个？

提示：之前讲过的归并排序，可不仅仅是归并排序这么简单，递归思想和归并的思想，它有大用处！`
看本文之前，必看之前的基础知识：全都是用归并的思想做！

（1）10大排序算法之四：归并排序【稳定的】，复杂度中，系统常用归并排序
(2）数组小和问题：用递归思想和归并排序求数组arr的数组小和

文章目录

• 求数组arr中的降序对有多少个？
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二、解题
• • 暴力解，面试0分
  • 递归思想，归并排序最优解
• 总结

题目

求数组arr中的降序对有多少个
降序对？比如 31,21，73等等
前面数字比后面的大，就是降序

一、审题

示例：3,1,7,0,2
对于3:31,30,31,3对
对于1:10，1对
对于7,70,72,2对
对于0，没有
对于2，没有
故总共5个降序对

二、解题

暴力解，面试0分

每次都去索引位置i，右边有几个比它小，统计降序对个数，o(n^2)复杂度
笔试可能AC一小部分，面试0分
手撕不是问题：

//暴力方法
    public static int invertedSeq1(int[] arr){
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[i]) num++;//遇见一个数比左边小则++，即逆序对一定出现了
            }
        }
        return num;
    }

递归思想，归并排序最优解

我们之前就说过，当但凡遇到求一个结果ans
它依赖：在位置i，左边或者右边，要找，比i位置的数，小的，或者大的，这种
完全可以用递归归并的思想做

本题，无非，就是遇到i位置，咱就是要o(1)速度找到，它右边有多少个数，比自己小？
这又是递归过程中，归并排序时，统计左边哪个数，比右边大，
这样就能发现，左边有mid-p1+1个比右边p2位置大，降序对个数ans+=mid-p1+1

now，我们来看一下流程：
整体统计函数mergeSortAndFindDescendPairs（arr， L, R）
（1）当L>=R，1个数，那不好意思，没有降序对，返回0
（2）先去左边部分L–mid上递归统计那部分有多少个降序对left；
（3）然后去右边部分mid–R上递归统计那部分有多少个降序对right；
（4）然后我们要merge这两部分，从L–mid–R上归并排序，与此同时统计左边每个位置p1，能有多少个降序对，统计结果为cur
——当p1位置>p2位置时，cur+=mid-p1+1个，然后将p1位置搬移到help上，继续看看还有没有数，比右边大的
——如果p1位置<=p2位置时：没法产生降序对，则直接让p2位置搬移到help，方便看还有没数能组成降序对
（5）返回left+right=cur
看图：

是不是跟数组小和极其相似
区别就在，我们到底是要升序呢？还是要降序，就这么简单！！！！！！
举例说明：1 3 7 0 2
（1）p1为0，p2为3，此时1>0，则说明1 3 7 均>0，故有mid-p1+1=3个大于0，降序对增加3，p2++=4
（2）此时1<2，故没法组合降序对，啥也不增加，p1++=1
（）此时3>2，则说明3 7 均>2，故有mid-p1+1=2个大于0，降序对增加2，p2++=5
stop 将升序的3 7 搬移到help
转移到arr中，返回结果cur=5

这里唯一要理解的就是当左边<=右边时，不需要统计降序对，同时得让p1++，尝试找到左边>右边的情况
既然有左边>右边，就应该让p2++，目的是看看还有没有其它p1在前面时的逆序对。
比如：

手撕代码：

//复习，统计逆序对，跟数组小和一个道理
    public static int mergeCount(int[] arr, int L, int mid, int R){
        if (L == R) return 0;//1个数，没有降序对

        //至少2个数
        int p1 = L;
        int p2 = mid + 1;
        int[] help = new int[R - L + 1];
        int i = 0;//help 索引
        int ans = 0;//降序对的个数

        while (p1 <= mid && p2 <= R){
            //先统计，咱再排序，左边大，才有降序对
            ans += arr[p1] <= arr[p2] ? 0 : mid - p1 + 1;
            //正常排序，只要是<=就搬动p1，不统计降序对，看看还有没有可能找到新的p1比p2大的
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //剩下的，谁没有就copy
        while (p1 <= mid) help[i++] = arr[p1++];
        while (p2 <= R) help[i++] = arr[p2++];

        //转移
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }

        return ans;
    }
    //递归调用，left，right，然后merge
    public static int mergeSortAndFindDescendPairs(int[] arr, int L, int R){
        if (L >= R) return 0;//如果就1个数，没法组成逆序对

        //至少两个
        int mid = L + ((R - L) >> 1);
        int left = mergeSortAndFindDescendPairs(arr, L, mid);
        int right = mergeSortAndFindDescendPairs(arr, mid + 1, R);
        int cur = mergeCount(arr, L, mid, R);

        return left + right + cur;
    }

    //简单测试
    public static void test(){
        int[] arr = {7,1,2,3,4,5,1};//显然逆序对为71,72,73,74只有4个
        int[] arr2 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr2[i] = arr[i];//copy一份
        }
        int[] arr3 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr3[i] = arr[i];//copy一份
        }
        int num1 = invertedSeq1(arr);
        System.out.println(num1);
        int num2 = invertedSeq2(arr2);
        System.out.println(num2);
        int num3 = mergeSortAndFindDescendPairs(arr3, 0, arr3.length - 1);
        System.out.println(num3);
    }

对数器，上面一种，短一点，下面第2种验证：

//对数器之构建随机数组
    public static int[] createArray(int arrSize, int maxValue){
        int[] arr = new int[arrSize];
        for (int i = 0; i < arrSize; i++) {
            arr[i] = (int)(maxValue * Math.random());//0-N-1的随机数
        }
        return arr;
    }

    public static void checker(){
        //生成检验数组
        int[] arr = createArray(10000,10000);
        int[] arr2 = new int[arr.length];//赋值同样一个数组arr
        for (int i = 0; i < arr.length; i++) {
            arr2[i] = arr[i];//copy即可
        }
        int[] arr3 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr3[i] = arr[i];//copy一份
        }

        //绝对的正确方法——暴力方法，或系统函数，操作arr
        int num1 = invertedSeq1(arr);
        //这个暴力方法实在是太慢了************
        System.out.println("暴力方法结束！");
        //优化方法，操作arr2
        int num2 = invertedSeq2(arr2);
        //复习优化方法，操作arr3
        int num3 = mergeSortAndFindDescendPairs(arr3, 0, arr3.length - 1);

        //然后两个数组对位校验
        System.out.println((num1 != num2 || num1 != num3) ? "oops,wrong!" : "right!");
    }

    public static void main(String[] args) {
        checker();
        System.out.println();
        test();
    }

结果：

暴力方法结束！
right!

10
10
10

自然，归并排序的算法复杂度o(n*log(n))
比o(n^2)小吧，这就是最优解

总结

提示：重要经验：

1）再一次证明递归思想，归并排序的用处极其大，只要结果依赖寻找i位置左右比i小的，或者比i大的数，就可以用归并排序的思想
2）多熟悉这类题目，今后再见到类似的题目，一定要敏感地想到这个解决方案