剑指Offer(三十五):数组中的逆序对

  • 3
  • 672 °C
  • A+
所属分类:剑指Offer
摘要

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。

剑指Offer(三十五):数组中的逆序对

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。

输入描述:

题目保证输入的数组中没有的相同的数字

数据范围:

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

输入:

输出:

1、思路

如数组{7,5,6,4},逆序对总共有5对,{7,5},{7,6},{7,4},{5,4},{6,4};

思路1:暴力解法,顺序扫描整个数组,每扫描到一个数字的时候,逐个比较该数字和它后面的数字的大小。如果后面的数字比它小,则这两个数字就组成一个逆序对。假设数组中含有n个数字,由于每个数字都要和O(n)个数字作比较,因此这个算法的时间复杂度是O(n^2)。

思路2:分治思想,采用归并排序的思路来处理,如下图,先分后治:

剑指Offer(三十五):数组中的逆序对

先把数组分解成两个长度为2的子数组,再把这两个子数组分解成两个长度为1的子数组。接下来一边合并相邻的子数组,一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7>5,因此(7,5)组成一个逆序对。同样在第二对长度为1的子数组{6},{4}中也有逆序对(6,4),由于已经统计了这两对子数组内部的逆序对,因此需要把这两对子数组进行排序,避免在之后的统计过程中重复统计。

剑指Offer(三十五):数组中的逆序对

逆序对的总数 = 左边数组中的逆序对的数量 + 右边数组中逆序对的数量 + 左右结合成新的顺序数组时中出现的逆序对的数量

总结一下:

这是一个归并排序的合并过程,主要是考虑合并两个有序序列时,计算逆序对数。

对于两个升序序列,设置两个下标:两个有序序列的末尾。每次比较两个末尾值,如果前末尾大于后末尾值,则有”后序列当前长度“个逆序对;否则不构成逆序对。然后把较大值拷贝到辅助数组的末尾,即最终要将两个有序序列合并到辅助数组并有序。

这样,每次在合并前,先递归地处理左半段、右半段,则左、右半段有序,且左右半段的逆序对数可得到,再计算左右半段合并时逆序对的个数。

2、代码

C++:

注意:InversePairsCore形参的顺序是(data,copy),而递归调用时实参是(copy,data)。

要明白递归函数InversePairsCore的作用就行了,它是对data的左右半段进行合并,复制到辅助数组copy中有序。最后,data和copy两个数组都是有序的。

Python:

Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:3   其中:访客  2   博主  1

    • avatar 爱看的剧 来自天朝的朋友 谷歌浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4

      大哥 你这个表示很不清楚,不容易理解,建议增加以下内容:
      如上图在(a)图中:
      是两个排好序的数组,一个是5,7,另一个是4,6.
      我们用两个指针P1和P2,一个指向左边那么数组的未尾,一个指向右边那么数组的未尾。
      于是我们比较P1和P2所指向的这两个数,由于P1指向的数大于P2指向的数,又由于我们右
      边的那个数组是从小到大排好序的,于是逆序数就是P2加它左边的数=2了。然后我们将
      P1指向的数放入辅助数组中,用P3指示。P1左移一位。P2保持不动
      (b)图中:
      由于P1比P2小,因此此时P2指向的数无用了。因为P1应该是在左边的数组中属于最大的了
      于是将P2指向的数复制到P3。然后将P2左移一位。
      (C)图中:
      和(a) 图相似了。

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 联通

          @爱看的剧 感谢,你留言了,别人就能看到了,哈哈。

        • avatar 爱看的剧 来自天朝的朋友 谷歌浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4

          之所以交换copy和data的顺序是因为:
          首先data=copy,经过排序后data左半部分仍旧乱序,但copy左半部分已经存储了排好序的data左半部分,即已经保存了data左半部分的信息,这样在向上层递归时,data左半部分本身可以作为容器,copy左半部分作为已经排好序的一个单元,即代拍序列的一个元素。