当前位置：移动技术网 > IT编程>开发语言>Java > 小和问题（归并排序）

小和问题（归并排序）

2020年07月22日 | 移动技术网IT编程 | 我要评论

题目

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

描述：
[1, 3, 2, 51, 5]
1左边比1小的数 0；
3左边比3小的数 1；
2左边比2小的数 1；
51左边比51小的数 2,3,1；
5左边比5小的数 2,3,1；
所以小和为0+1+1+2+3+1+2+3+1=14;

解题思路

转换思想：上述例子我们要求5左面比5小的所有数的和可以转换成：
求1右面比1大的数的个数×1本身+3右面比3大的数个数×3本身**+2右面比2大的数的个数×2本身+51右面比51大的数的个数×51本身+5右面比5大的数的个数×**5本身。

如何理解？
上述例子中从1开始遍历求到5计算小和，那么1总共被加了4次因为3比1大，2比1大，51比1大，5比1大，所以就是1*4；同理每个元素的小和就是本身×后面比他大的个数，之后加起来就是最终答案。

如此一来问题转换为：
[1, 3, 2, 51, 5]
1右边比1大的个数本身 4×1=4；
3右边比3大的个数本身 3×2=6；
2右边比2大的个数本身 2×2=4；
51右边比51大的个数本身 5×1=0；
5右边比5大的个数*本身 5×0=0；
所以小和为4+6+4+0+0=14;

解决方案

暴力破解这里就不说了，双层for循环遍历判断右面数比左面大就计数++，时间复杂度为o（n的平方）。
本题还可以用归并排序处理。时间复杂度为o（n×logn）

在并的时候判断以上逻辑并且累加即可。

代码如下：


public class Main {
    private static int sum = 0;

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 51, 5};
        mergeSort(arr, 0, arr.length - 1);
        print_nums(arr);
        System.out.println();
        System.out.println(sum);
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + (r - l) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);

    }

    public static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int pl = l;
        int pr = mid + 1;
        int i = 0;
        while (pl <= mid && pr <= r) {
            sum += arr[pl] < arr[pr] ? (r - pr + 1) * arr[pl] : 0;
            help[i++] = arr[pl] < arr[pr] ? arr[pl++] : arr[pr++];
        }
        while (pl <= mid) {
            help[i++] = arr[pl++];
        }
        while (pr <= r) {
            help[i++] = arr[pr++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }

    public static void print_nums(int[] nums) {
        for (int i : nums) {
            System.out.print(i + " ");
        }
    }


}

同理也可以求数列的逆序数


/**
 * 数列逆序数 并输出是奇排列还是偶排列
 */
public class Main {
    private static int sum = 0;

    public static void main(String[] args) {
        int[] nums = {2,4,3,1};
        MergeSort(nums, 0, nums.length - 1);
       /* print_nums(nums);*/
        String s = checkIsEvenNumber(sum);
        System.out.println(s + ":" + sum);
    }

    public static void MergeSort(int[] nums, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        MergeSort(nums, l, mid);
        MergeSort(nums, mid + 1, r);
        Merge(nums, l, mid, r);
    }

    public static void Merge(int[] nums, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int pl = l;
        int pr = mid + 1;
        int i = 0;
        while (pl <= mid && pr <= r) {
            sum += nums[pl] > nums[pr] ? (r - pr + 1) : 0;
            help[i++] = nums[pl] > nums[pr] ? nums[pl++] : nums[pr++];
        }
        while (pl <= mid) {
            help[i++] = nums[pl++];
        }
        while (pr <= r) {
            help[i++] = nums[pr++];
        }
        for (i = 0; i < help.length; i++) {
            nums[l + i] = help[i];
        }
    }

    public static String checkIsEvenNumber(int num) {
        return num % 2 == 0 ? "偶排列" : "奇排列";
    }

  /*  public static void print_nums(int[] nums) {
        for (int i : nums) {
            System.out.print(i + " ");
        }
    }*/


}

本文地址：https://blog.csdn.net/qq_35416214/article/details/107475524