深圳网站制作的网站推广方案策划

题目

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

描述：
[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 + " ");}}*/}