首页 > 编程语言 > 详细

体育彩票31选7:数组中的逆序对

时间:2018-06-22 10:13:20      阅读:77      评论:0      收藏:0      [点我收藏+]

31选7中奖规则 www.ojmb.com.cn 标签:之间   逆序   bsp   next   归并排序   img   对数   http   归并   

题目:在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

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

 

更快的算法

我们可以考虑比较两个相邻的数字,过程如下图所示:

 技术分享图片

 

如图(a)和图(b)所示,我们先把数组分解成两个长度为2的子数组,再把这两个子数组分别拆分成两个长度为1的子数组。接下来一边合并相邻的子数组,一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5,因此(7,5)组成一个逆序对,同样在第二对长度为1的子数组{6}、{4}中也有逆序对(6,4)。由于我们已经统计了这两对子数组内部的逆序对,因此需要把这两对子数组排序,以免在以后的统计过程中再重复统计。

 技术分享图片

 

注:图中省略了最后一步,即复制第二个子数组最后剩余的4到辅助数组中.(a)P1指向的数字大于P2指向的数字,表明数组中存在的逆序对。P2指向的数字是第二个子数组的第二个数字,因此第二个子数组中有两个数字比7小。把逆序对数目加2,并把7复制到辅助数组,向前移动P1和P3。(b)P1指向的数字小于P2指向的数字,没有逆序对,把P2指向的数字复制到辅助数组,并向前移动P2和P3。(c)P1指向的数字大于P2指向的数字,因此存在逆序对,由于P2指向的数字是第二个子数组的第一个数字,子数组中只有一个数字比5小,把逆序对数目加1,并把5复制到辅助数组,向前移动P1和P3.

统计逆序对的规律:先把数组分割成子数组,先统计出子数组内部的逆序对的数目,然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中,还需要对数组进行排序。如果对排序算法很熟悉,我们不难发现这个排序的过程实际上就是归并排序。

 

两个链表的第一个公共结点

题目:输入两个链表,找出它们的第一个公共结点。链表结点定义如下:

这两个链表是单向链表。如果两个单向链表有公共的结点,那么这两个链表从某一结点开始,他们的m_pNext都指向同一个结点。但由于是单向链表的结点,每一个结点只有一个m_pNext,因此从第一个公共结点开始,之后他们所有结点都是重合的,不可能再出现分叉。所以两个有公共结点而部分重合的链表,拓扑形状看起来像一个Y,而不可能像X.如下图所示:

 技术分享图片

 

分别把两个链表的结点放入两个栈里,这样两个链表的尾结点就位与两个栈的栈顶,接下来比较两个栈顶的结点是否相同。如果相同,则把栈顶弹出接着比较下一个栈顶,直到找到最后一个相同的结点。

 

数组中的逆序对

标签:之间   逆序   bsp   next   归并排序   img   对数   http   归并   

原文:https://www.cnblogs.com/zhibei/p/9211835.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
? 2014 31选7中奖规则 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号