归并排序-面试例子

小数和问题

描述

在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。

例子

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

非递归

public static int smallSum(int [] arr){if(arr == null || arr.length <2)return 0;int [] help = new int[arr.length];int step = 1;int N = arr.length;int L = 0;int ans = 0;while (step < N){L = 0;while (L < N){//左组最后一个数位置int m = L + step - 1;if(m >= N){break;}if(step >= N - L){break;}int R = Math.min(m+step,N-1);ans += merge(arr,L,m,R,help);L = R + 1;}if(step > N/2){break;}step <<= 1;}return ans;}public static int merge(int[] arr,int l,int m,int r,int [] help){//help indexint i = 0;//p1 左侧开始index,p2 右侧开始indexint p1 = l;int p2 = m+1;//结果保存int ans = 0;while (p1 <= m && p2 <= r){ans += arr[p1]<arr[p2]?arr[p1] *(r-p2+1):0;help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];}while (p1 <= m){help[i++] = arr[p1++];}while (p2 <= r){help[i++] = arr[p2++];}for (i = 0; i < r-l+1 ; i++) {arr[l+i] = help[i];}return ans;}

递归

    public static int progress(int [] arr,int l,int r,int [] help){if(l == r)return 0;int m = l + ((r -l) >> 1);return progress(arr,l,m,help)+ progress(arr,m+1,r,help)+ merge(arr,l,m,r,help);}

逆序对问题

描述

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

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

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

(1,0)

(4,3),(4,1)

(3,1)

code

    //递归public static int reversePair(int [] arr){if(arr == null || arr.length <2)return 0;return progress(arr,0,arr.length -1);}public static int progress(int [] arr,int l,int r){if(l == r)return 0;int m = l + ((r-l)>>1);return progress(arr,l,m)+progress(arr,m+1,r)+merge(arr,l,m,r);}//非递归public static int reversePair2(int [] arr){if(arr == null || arr.length < 2)return 0;int ans = 0;int L = 0;int N = arr.length;int step = 1;while (step < N){L = 0;while (L < N){if(L+step >= N)break;int m = L + step - 1;if(m >= N)break;int r = Math.min(N-1,m+step);int temp = merge(arr,L,m,r);ans += temp;L = r + 1;}if(step > N/2)break;step <<= 1;}return ans;}public static int merge(int [] arr,int L,int M,int R){// 先算有多少逆序对// 和归并过程分离int res = 0;int p = M + 1;for (int i = L; i <= M; i++) {while (p <= R && arr[i] > arr[p]) {p++;}res += p - (M + 1);}// 下面完全和归并排序一样int[] help = new int[R - L + 1];int i = 0;int p1 = L;int p2 = M + 1;while (p1 <= M && p2 <= R) {help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}// 要么p1越界了，要么p2越界了while (p1 <= M) {help[i++] = arr[p1++];}while (p2 <= R) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}return res;}

左边大于右边倍数的数

描述

在一个数组中，
对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数
比如：[3,1,7,0,2]
3的后面有：1，0
1的后面有：0
7的后面有：0，2
0的后面没有
2的后面没有
所以总共有5个

思路

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

code

//递归public static int biggerThatRightTwice(int []arr){if(arr == null || arr.length<2){return 0;}return progress(arr,0,arr.length-1);}public static int progress(int[] arr,int l,int r){if(l == r){return 0;}int m = l + ((r-l)>>1);System.out.println("l,m,r:"+l+","+m+","+r);return progress(arr,l,m)+progress(arr,m+1,r)+merge(arr,l,m,r);}//非递归public static int biggerThatRightTwice2(int [] arr){if(arr == null || arr.length <2)return 0;int L = 0;int step = 1;int N = arr.length;int ans = 0;while (step < N){L = 0;while (L < N){if(step >= N-L)break;int m = L + step - 1;if(m >= N)break;int r = Math.min(m+step,N-1);ans += merge(arr,L,m,r);L  = r + 1;}if(step > N/2)break;step <<=1;}return ans;}public static int merge(int[] arr,int l,int m,int r){//[l,m] [m+1,r]进行归并，其中[l,m],[m+1,r]分别已经有序//先计算int p1 = l,p2 = m+1;int ans = 0;//左侧遍历lwhile (p1 <= m){//右侧遍历while (p2 <= r){//如果左侧 > 右侧 * 2，则继续判断，知道不满足条件//当不满足条件时，则右侧从开始位置m+1到p2位置为p1满足条件的数if(arr[p1] > arr[p2] *2){p2++;}else{break;}}//p2 - (m+1) => [m+1,p2) 即从m+1到p2个元素个数，不包含p2ans += (p2 - (m+1));p1++;}//再进行归并int [] help = new int[r-l+1];int i = 0;p1 = l;p2 = m+1;while (p1<=m && p2<=r){help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];}while (p1<=m){help[i++] = arr[p1++];}while (p2<=r){help[i++] = arr[p2++];}for(i=0;i<help.length;i++){arr[l+i] = help[i];}return ans;}