在一个数组中,一个数左边比它小的数的总和,叫数的小和,所有数的小和累加起来,叫数组小和。求数组小和。 例子: [1,3,4,2,5] 1左边比1小的数:没有 3左边比3小的数:1 4左边比4小的数:1、3 2左边比2小的数:1 5左边比5小的数:1、3、4、 2 所以数组的小和为1+1+3+1+1+3+4+2=16
思路:
1 有几个数比a大就产生几个a 累加结果与题一样
2 根据归并递归后,递归到2个的时候
1 如果左面的小
这时候 累加要算左边的数
2 如果 右边的小
这时候交换位置不累加
3 根据归并 递归 到4个数的时候
13 24
1比2小 要 累加2个1 (因为4页比1大)
结果 1
3比2大 交换位置 不做累加
结果1234
代码
package class04; public class Code02_SmallSum { public static int smallSum(int[] arr) { if (arr == null || arr.length < 2) { return 0; } return process(arr, 0, arr.length - 1); } // arr[L..R]既要排好序,也要求小和返回 // 所有merge时,产生的小和,累加 // 左 排序 merge // 右 排序 merge // merge public static int process(int[] arr, int l, int r) { if (l == r) { return 0; } // l < r int mid = l + ((r - l) >> 1); return //左边小和总量 process(arr, l, mid) + //右边边小和总量 process(arr, mid + 1, r) + //合并小和总量 merge(arr, l, mid, r); } public static int merge(int[] arr, int L, int m, int r) { int[] help = new int[r - L + 1]; int i = 0; int p1 = L; int p2 = m + 1; int res = 0; while (p1 <= m && p2 <= r) { //在左组小于右组数的时候,产生 (r - p2 + 1) 个左组当前p1 (r - p2 + 1)是右组大与左组p1 的数的个数 res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 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 < help.length; i++) { arr[L + i] = help[i]; } return res; } // for test public static int comparator(int[] arr) { if (arr == null || arr.length < 2) { return 0; } int res = 0; for (int i = 1; i < arr.length; i++) { for (int j = 0; j < i; j++) { res += arr[j] < arr[i] ? arr[j] : 0; } } return res; } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); if (smallSum(arr1) != comparator(arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)