• 归并排序-面试例子

    小数和问题

    描述
    在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。
    例子
    5 2 6 1 7
小和原始的求法是：任何一个数左边比它小的数累加起来。
5左边比它小数累加：0
2左边比它小数累加：0
6左边比它小数累加：5 + 2 = 7
1左边比它小数累加：0
7左边比它小数累加：5 + 2 + 6 + 1 = 14
总共21。
    思路
    如果左侧某数a比右侧某数b小，则在求b的小和的时候，肯定会累加一个a，即sum+=a。
反过来，在遍历到a的时候，如果我们知道右侧有几个数比a大，则可以提前知道会累加几个a
使用归并排序时恰好有左右对比操作，所以使用归并排序来做
即：
每个数右边比它大的数的个数 * 这个数自身
所以：
在原来归并排序的基础上，增加一个ans用于记录结果
在进行归并时左侧<右侧时产生小数 n * number
    小和求法还可以是：每个数右边比它大的数的个数 * 这个数自身

5 2 6 1 7
5的右边比它大的数的个数：2个（6和7），所以产生：2个 * 5 = 10
2的右边比它大的数的个数：2个（6和7），所以产生：2个 * 2 = 4
6的右边比它大的数的个数：1个（7），所以产生：1个 * 6 = 6
1的右边比它大的数的个数：1个（7），所以产生：1个 * 1 = 1
7的右边比它大的数的个数：0个，所以产生：0个 * 7 = 0
总共21。
    code

    非递归

    1.  
    2.     public static int smallSum(int [] arr){
    3.         if(arr == null || arr.length <2)
    4.             return 0;
    5.  
    6.         int [] help = new int[arr.length];
    7.         int step = 1;
    8.         int N = arr.length;
    9.         int L = 0;
    10.         int ans = 0;
    11.  
    12.         while (step < N){
    13.             L = 0;
    14.             while (L < N){
    15.                 //左组最后一个数位置
    16.                 int m = L + step - 1;
    17.                 if(m >= N){
    18.                     break;
    19.                 }
    20.                 if(step >= N - L){
    21.                     break;
    22.                 }
    23.                 int R = Math.min(m+step,N-1);
    24.                 ans += merge(arr,L,m,R,help);
    25.  
    26.                 L = R + 1;
    27.             }
    28.             if(step > N/2){
    29.                 break;
    30.             }
    31.             step <<= 1;
    32.         }
    33.         return ans;
    34.     }
    35.  
    36.     public static int merge(int[] arr,int l,int m,int r,int [] help){
    37.         //help index
    38.         int i = 0;
    39.         //p1 左侧开始index,p2 右侧开始index
    40.         int p1 = l;
    41.         int p2 = m+1;
    42.         //结果保存
    43.         int ans = 0;
    44.         while (p1 <= m && p2 <= r){
    45.             ans += arr[p1]1):0;
    46.             help[i++] = arr[p1]
    47.         }
    48.         while (p1 <= m){
    49.             help[i++] = arr[p1++];
    50.         }
    51.         while (p2 <= r){
    52.             help[i++] = arr[p2++];
    53.         }
    54.         for (i = 0; i < r-l+1 ; i++) {
    55.             arr[l+i] = help[i];
    56.         }
    57.         return ans;
    58.     }

    递归

    1.     public static int progress(int [] arr,int l,int r,int [] help){
    2.  
    3.         if(l == r)
    4.             return 0;
    5.         int m = l + ((r -l) >> 1);
    6.  
    7.         return progress(arr,l,m,help)
    8.                 + progress(arr,m+1,r,help)
    9.                 + merge(arr,l,m,r,help);
    10.     }

    逆序对问题

    描述
    一个数组中，左边的数比右边的数大，求有多少个这样的组合

    比如  [3,1,0,4,3,1] 有7个逆序对，分别是

    (3,1),(3,0),(3,1)

    (1,0)

    (4,3),(4,1)

    (3,1)

    code
    1.     //递归
    2.     public static int reversePair(int [] arr){
    3.         if(arr == null || arr.length <2)return 0;
    4.  
    5.         return progress(arr,0,arr.length -1);
    6.     }
    7.     public static int progress(int [] arr,int l,int r){
    8.         if(l == r)return 0;
    9.         int m = l + ((r-l)>>1);
    10.         return progress(arr,l,m)
    11.                 +progress(arr,m+1,r)
    12.                 +merge(arr,l,m,r);
    13.     }
    14.  
    15.     //非递归
    16.     public static int reversePair2(int [] arr){
    17.         if(arr == null || arr.length < 2)return 0;
    18.  
    19.         int ans = 0;
    20.         int L = 0;
    21.         int N = arr.length;
    22.         int step = 1;
    23.         while (step < N){
    24.             L = 0;
    25.             while (L < N){
    26.                 if(L+step >= N)break;
    27.                 int m = L + step - 1;
    28.                 if(m >= N)break;
    29.                 int r = Math.min(N-1,m+step);
    30.                 int temp = merge(arr,L,m,r);
    31.                 ans += temp;
    32.                 L = r + 1;
    33.             }
    34.             if(step > N/2)break;
    35.             step <<= 1;
    36.         }
    37.         return ans;
    38.     }
    39.     public static int merge(int [] arr,int L,int M,int R){
    40.         // 先算有多少逆序对
    41.         // 和归并过程分离
    42.         int res = 0;
    43.         int p = M + 1;
    44.         for (int i = L; i <= M; i++) {
    45.             while (p <= R && arr[i] > arr[p]) {
    46.                 p++;
    47.             }
    48.             res += p - (M + 1);
    49.         }
    50.         // 下面完全和归并排序一样
    51.         int[] help = new int[R - L + 1];
    52.         int i = 0;
    53.         int p1 = L;
    54.         int p2 = M + 1;
    55.         while (p1 <= M && p2 <= R) {
    56.             help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    57.         }
    58.         // 要么p1越界了，要么p2越界了
    59.         while (p1 <= M) {
    60.             help[i++] = arr[p1++];
    61.         }
    62.         while (p2 <= R) {
    63.             help[i++] = arr[p2++];
    64.         }
    65.         for (i = 0; i < help.length; i++) {
    66.             arr[L + i] = help[i];
    67.         }
    68.         return res;
    69.     }

    左边大于右边倍数的数

    描述
    在一个数组中，
对于每个数num，求有多少个后面的数 * 2 依然 

    思路
     

    右边有多少个数*2比左边的数小
在归并排序过程中，分组后左侧有序，右侧有序，在进行左右侧合并时，统计验证关系【2倍关系】
这样可以得到该左侧位置相对于右侧位置的2倍关系统计和
     

    code
     

    1.  
    2.     //递归
    3.     public static int biggerThatRightTwice(int []arr){
    4.         if(arr == null || arr.length<2){
    5.             return 0;
    6.         }
    7.         return progress(arr,0,arr.length-1);
    8.     }
    9.     public static int progress(int[] arr,int l,int r){
    10.         if(l == r){
    11.             return 0;
    12.         }
    13.         int m = l + ((r-l)>>1);
    14.         System.out.println("l,m,r:"+l+","+m+","+r);
    15.  
    16.         return progress(arr,l,m)
    17.                 +progress(arr,m+1,r)
    18.                 +merge(arr,l,m,r);
    19.     }
    20.  
    21.     //非递归
    22.     public static int biggerThatRightTwice2(int [] arr){
    23.        if(arr == null || arr.length <2)return 0;
    24.  
    25.        int L = 0;
    26.        int step = 1;
    27.        int N = arr.length;
    28.        int ans = 0;
    29.        while (step < N){
    30.            L = 0;
    31.            while (L < N){
    32.                if(step >= N-L)break;
    33.                int m = L + step - 1;
    34.                if(m >= N)break;
    35.                int r = Math.min(m+step,N-1);
    36.                ans += merge(arr,L,m,r);
    37.                L  = r + 1;
    38.            }
    39.            if(step > N/2)break;
    40.            step <<=1;
    41.        }
    42.        return ans;
    43.     }
    44.     public static int merge(int[] arr,int l,int m,int r){
    45.         //[l,m] [m+1,r]进行归并，其中[l,m],[m+1,r]分别已经有序
    46.  
    47.         //先计算
    48.         int p1 = l,p2 = m+1;
    49.         int ans = 0;
    50.         //左侧遍历l
    51.        while (p1 <= m){
    52.             //右侧遍历
    53.             while (p2 <= r){
    54.                 //如果左侧 > 右侧 * 2，则继续判断，知道不满足条件
    55.                 //当不满足条件时，则右侧从开始位置m+1到p2位置为p1满足条件的数
    56.                 if(arr[p1] > arr[p2] *2){
    57.                     p2++;
    58.                 }else{
    59.                     break;
    60.                 }
    61.             }
    62.             //p2 - (m+1) => [m+1,p2) 即从m+1到p2个元素个数，不包含p2
    63.             ans += (p2 - (m+1));
    64.             p1++;
    65.         }
    66.         //再进行归并
    67.         int [] help = new int[r-l+1];
    68.         int i = 0;
    69.         p1 = l;
    70.         p2 = m+1;
    71.         while (p1<=m && p2<=r){
    72.             help[i++] = arr[p1]
    73.         }
    74.         while (p1<=m){
    75.             help[i++] = arr[p1++];
    76.         }
    77.         while (p2<=r){
    78.             help[i++] = arr[p2++];
    79.         }
    80.         for(i=0;i
    81.             arr[l+i] = help[i];
    82.         }
    83.         return ans;
    84.     }
  • 相关阅读:
    数据结构——树
    js数组操作——对象数组根据某个相同的字段分组
    【接口自动化测试入门】接口测试基础（超详细~）
    「零基础从零开始写VO视觉里程计」G2O基础知识讲解（7-5）
    准入控制器(Admission Controller):ResourceQuota，ImagePolicyWebhook
    解决HBuilderX无法登录的问题
    Dubbo反序列化漏洞分析集合
    Apacha Flume
    【无标题】
    Java服务启动报Unsupported record version Unknown-0.0
  • 原文地址：https://blog.csdn.net/hey_lie/article/details/132741871