Code13 数组中左边大于2倍右边数的总对数

本文主要是介绍Code13 数组中左边大于2倍右边数的总对数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数组
[6,4,2,1]
其中(6,2)(6,1)(4,1)这3个组合是满足左边大于右边数的两倍

核心代码块，建立在归并排序的基础上

 int ans = 0;int windowR = M+1;for (int j = L;j<=M;j++){while (windowR <= R && arr[j] > (arr[windowR]*2)){windowR ++;}ans += windowR - (M+1);}

public static int biggerThanRightTwice(int [] arr){if(arr == null || arr.length <2){return 0;}return process(arr,0,arr.length-1);}public static int process(int [] arr ,int L,int R){if(L == R){return 0;}int M = L + ((R-L) >> 1);return process(arr,L,M)+process(arr,M+1,R)+merge(arr,L,M,R);}public static int merge(int [] arr ,int L,int M,int R){int ans = 0;int windowR = M+1;for (int j = L;j<=M;j++){while (windowR <= R && arr[j] > (arr[windowR]*2)){windowR ++;}ans += windowR - (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++];}while (p1 <= M){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;}

这篇关于Code13 数组中左边大于2倍右边数的总对数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---