本文共 2194 字，大约阅读时间需要 7 分钟。

算法–小和/逆序对问题

问题描述：

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

例子： [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.暴力求解

代码如下：

public static int Sum(int[] nums)        {
               int sum = 0;            for (int i = 1; i < nums.Length; i++)            {
                   for (int j = 0; j < i; j++)                {
                       if (nums[j] < nums[i])                        sum += nums[j];                }            }            return sum;        }

2.归并排序的思想

求小和思路：

在归并排序的基础上只增加了一行代码，相当于搭了归并排序的顺风车。在两个元素归并之前，对其进行比较，如果左指针指向的元素小于右指针指向的元素，则两者构成小和。又因为右指针指向的元素的右侧元素均大于左指针指向的元素，故构成的小和应为（左指针指向元素值 * 右指针及其之后的元素个数）。

求逆序对的思路同理。

代码如下：

public static int sum;		public static int count;        static void Main(string[] args)        {
               int[] nums = {
    1, 3, 4, 2, 5 };            MergeSort(nums, 0, nums.Length - 1);            Console.WriteLine(sum);            Console.Write(count);            Console.ReadKey();        }        // 归并排序        public static void MergeSort(int[] nums,int low,int high)        {
               if (low < high)            {
                   int mid = (low + high) / 2;                MergeSort(nums, low, mid);                MergeSort(nums, mid + 1, high);                Merge(nums, low, mid, high);            }        }        public static void Merge(int[] nums, int low, int mid, int high)        {
               int[] temp = new int[high - low + 1];            int p1 = low;            int p2 = mid + 1;            int i = 0;            while (p1 <= mid && p1 <= high)            {
                   // 求小和                sum += nums[p1] < nums[p2] ? nums[p1] * (high - p2 + 1) : 0;                // 求逆序对的个数                count += nums[p1] > nums[p2] ? mid - p1 + 1 : 0;                temp[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];            }            while (p1 <= mid) temp[i++] = nums[p1++];            while (p2 <= high) temp[i++] = nums[p2++];            for (i = 0; i < temp.Length; i++)            {
                   nums[low + i] = temp[i];            }        }

输出结果：162

总结

绝大多数人都能想到暴力求解的思路，但其时间复杂度是O(n²)；采用归并排序的思想，时间复杂度能降到O(n*logn)。

转载地址：https://blog.csdn.net/weixin_45027619/article/details/115637434 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！