海东企业网站建设,企业网站托管服务常用指南,wordpress altair,南京中建乡旅建设投资有限公司网站小数和问题
描述
在一个数组中#xff0c;一个数左边比它小的数的总和#xff0c;叫数的小和#xff0c;所有数的小和累加起来#xff0c;叫数组小和。求数组小和。
例子
5 2 6 1 7
小和原始的求法是#xff1a;任何一个数左边比它小的数累加起来。
5左边比它小数累加…小数和问题
描述
在一个数组中一个数左边比它小的数的总和叫数的小和所有数的小和累加起来叫数组小和。求数组小和。
例子
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即suma。
反过来在遍历到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(mstep,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 m1;//结果保存int ans 0;while (p1 m p2 r){ans arr[p1]arr[p2]?arr[p1] *(r-p21):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-l1 ; i) {arr[li] 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,m1,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,m1,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(Lstep N)break;int m L step - 1;if(m N)break;int r Math.min(N-1,mstep);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的后面有10
1的后面有0
7的后面有02
0的后面没有
2的后面没有
所以总共有5个
思路
右边有多少个数*2比左边的数小
在归并排序过程中分组后左侧有序右侧有序在进行左右侧合并时统计验证关系【2倍关系】
这样可以得到该左侧位置相对于右侧位置的2倍关系统计和
code
//递归public static int biggerThatRightTwice(int []arr){if(arr null || arr.length2){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,m1,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(mstep,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] [m1,r]进行归并其中[l,m],[m1,r]分别已经有序//先计算int p1 l,p2 m1;int ans 0;//左侧遍历lwhile (p1 m){//右侧遍历while (p2 r){//如果左侧 右侧 * 2则继续判断知道不满足条件//当不满足条件时则右侧从开始位置m1到p2位置为p1满足条件的数if(arr[p1] arr[p2] *2){p2;}else{break;}}//p2 - (m1) [m1,p2) 即从m1到p2个元素个数不包含p2ans (p2 - (m1));p1;}//再进行归并int [] help new int[r-l1];int i 0;p1 l;p2 m1;while (p1m p2r){help[i] arr[p1]arr[p2]?arr[p1]:arr[p2];}while (p1m){help[i] arr[p1];}while (p2r){help[i] arr[p2];}for(i0;ihelp.length;i){arr[li] help[i];}return ans;}
