Java 小和问题

左手的ㄟ右手 2021-10-19 16:18 176阅读 0赞

![1548789-20190629233755511-1054680507.png][]

这题明明就是一个计数题，活生生变成了排序，为什么排序后还可以进行计数而不影响计数结果，因为排序之前大的那部分已经计算过了，以后的递归过程已经调用不到了，所以排序不会影响后面的计数

具体代码如下：

1 public class SmallSum {
      2 
      3     public static int smallSum(int[] arr) {
      4         if (arr == null || arr.length < 2) {
      5             return 0;
      6         }
      7         return mergeSort(arr, 0, arr.length - 1);
      8     }
      9 
     10     public static int mergeSort(int[] arr, int l, int r) {
     11         if (l == r) {
     12             return 0;
     13         }
     14         int mid = l + ((r - l) >> 1);
     15         return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
     16     }
     17 
     18     public static int merge(int[] arr, int l, int m, int r) {
     19         int[] help = new int[r - l + 1];
     20         int i = 0;
     21         int p1 = l;
     22         int p2 = m + 1;
     23         int res = 0;
     24         while (p1 <= m && p2 <= r) {
     25             res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
     26             help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
     27         }
     28         while (p1 <= m) {
     29             help[i++] = arr[p1++];
     30         }
     31         while (p2 <= r) {
     32             help[i++] = arr[p2++];
     33         }
     34         for (i = 0; i < help.length; i++) {
     35             arr[l + i] = help[i];
     36         }
     37         return res;
     38     }
     39 
     40     // for test
     41     public static int comparator(int[] arr) {
     42         if (arr == null || arr.length < 2) {
     43             return 0;
     44         }
     45         int res = 0;
     46         for (int i = 1; i < arr.length; i++) {
     47             for (int j = 0; j < i; j++) {
     48                 res += arr[j] < arr[i] ? arr[j] : 0;
     49             }
     50         }
     51         return res;
     52     }
     53 
     54     // for test
     55     public static int[] generateRandomArray(int maxSize, int maxValue) {
     56         int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
     57         for (int i = 0; i < arr.length; i++) {
     58             arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
     59         }
     60         return arr;
     61     }
     62 
     63     // for test
     64     public static int[] copyArray(int[] arr) {
     65         if (arr == null) {
     66             return null;
     67         }
     68         int[] res = new int[arr.length];
     69         for (int i = 0; i < arr.length; i++) {
     70             res[i] = arr[i];
     71         }
     72         return res;
     73     }
     74 
     75     // for test
     76     public static boolean isEqual(int[] arr1, int[] arr2) {
     77         if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
     78             return false;
     79         }
     80         if (arr1 == null && arr2 == null) {
     81             return true;
     82         }
     83         if (arr1.length != arr2.length) {
     84             return false;
     85         }
     86         for (int i = 0; i < arr1.length; i++) {
     87             if (arr1[i] != arr2[i]) {
     88                 return false;
     89             }
     90         }
     91         return true;
     92     }
     93 
     94     // for test
     95     public static void printArray(int[] arr) {
     96         if (arr == null) {
     97             return;
     98         }
     99         for (int i = 0; i < arr.length; i++) {
    100             System.out.print(arr[i] + " ");
    101         }
    102         System.out.println();
    103     }
    104 
    105     // for test
    106     public static void main(String[] args) {
    107         int testTime = 500000;
    108         int maxSize = 100;
    109         int maxValue = 100;
    110         boolean succeed = true;
    111         for (int i = 0; i < testTime; i++) {
    112             int[] arr1 = generateRandomArray(maxSize, maxValue);
    113             int[] arr2 = copyArray(arr1);
    114             if (smallSum(arr1) != comparator(arr2)) {
    115                 succeed = false;
    116                 printArray(arr1);
    117                 printArray(arr2);
    118                 break;
    119             }
    120         }
    121         System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    122     }
    123 
    124 }

转载于:https://www.cnblogs.com/leio123/p/11108312.html

[1548789-20190629233755511-1054680507.png]: /images/20211019/4774211434134a99b48060462f223ee4.png