剑指offer 36 数组中的逆序对

转载请注明出处:http://blog.csdn.net/ns_code/article/details/27520535

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

每个测试案例包括两行:

第一行包含一个整数n,表示数组中的元素个数。其中1 <= n <= 10^5。

第二行包含n个整数,每个数组均为int类型。

输出:对应每个测试案例,输出一个整数,表示数组中的逆序对的总数。样例输入:

4
7 5 6 4

样例输出:

5

    思路:最简单的方法是顺序数组,将每个数字与后面的比较,统计逆序对的个数,这种方法的时间复杂度为O(n*n),这种方法写出的代码在九度OJ上测试,会超时。剑指offer给出了归并排序的思路,这个有点难想到啊,也可能是我太弱了,根本没往这方面想!理解了思路,就不难了,将数组划分成两个子数组,再将子数组分别划分成两个子数组,统计每个子数组内的逆序对个数,并将其归并排序,再统计两个子数组之间的逆序对个数,并进行归并排序。这就是归并排序的变种,在归并排序代码的基础上稍作改进即可。

    合理还要注意一点:全局变量count不能声明为int型,必须为long long型。因为题目中说数组最大为10^5,那么最大逆序对为(10^5-1)*10^5/2,这个数大约在50亿左右,超过了int型的表示范围。

    AC代码如下:

[cpp] view plaincopy

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. /*
  4. 统计两个子数组之间的逆序对
  5. */
  6. long long MergePairsBetweenArray(int *arr,int *brr,int start,int mid,int end)  
  7. {  
  8. int i = mid;  
  9. int j = end;  
  10. int k = end;  //辅助数组的最后一位
  11. long long count = 0;  
  12. //设置两个指针i,j分别从右往左依次比较,
  13. //将较大的依次放入辅助数组的右边
  14. while(i>=start && j>=mid+1)  
  15.     {  
  16. if(arr[i] > arr[j])  
  17.         {  
  18.             count += j-mid;  
  19.             brr[k--] = arr[i--];  
  20.         }  
  21. else
  22.             brr[k--] = arr[j--];  
  23.     }  
  24. //将其中一个数组中还剩下的元素拷贝到辅助数组中,
  25. //两个循环只会执行其中的一个
  26. while(i>=start)  
  27.         brr[k--] = arr[i--];  
  28. while(j>=mid+1)  
  29.         brr[k--] = arr[j--];  
  30. //从辅助数组中将元素拷贝到原数组中,使其有序排列
  31. for(i=end;i>k;i--)  
  32.         arr[i] = brr[i];  
  33. return count;  
  34. }  
  35. /*
  36. 统计数组中的所有的逆序对
  37. */
  38. long long CountMergePairs(int *arr,int *brr,int start,int end)  
  39. {  
  40. long long PairsNum = 0;  
  41. if(start<end)  
  42.     {  
  43. int mid = (start+end)>>1;  
  44.         PairsNum += CountMergePairs(arr,brr,start,mid); //统计左边子数组的逆序对
  45.         PairsNum += CountMergePairs(arr,brr,mid+1,end); //统计右边子数组的逆序对
  46.         PairsNum += MergePairsBetweenArray(arr,brr,start,mid,end); //统计左右子数组间的逆序对
  47.     }  
  48. return PairsNum;  
  49. }  
  50. /*
  51. 将函数封装起来
  52. */
  53. long long CountTotalPairs(int *arr,int len)  
  54. {  
  55. if(arr==NULL || len<2)  
  56. return 0;  
  57. int *brr = (int *)malloc(len*sizeof(int));  
  58. if(brr == NULL)  
  59.         exit(EXIT_FAILURE);  
  60. long long sum = CountMergePairs(arr,brr,0,len-1);  
  61.     free(brr);  
  62.     brr = NULL;  
  63. return sum;  
  64. }  
  65. int main()  
  66. {  
  67. int n;  
  68. while(scanf("%d",&n) != EOF)  
  69.     {  
  70. int *arr = (int *)malloc(n*sizeof(int));  
  71. if(arr == NULL)  
  72.             exit(EXIT_FAILURE);  
  73. int i;  
  74. for(i=0;i<n;i++)  
  75.             scanf("%d",arr+i);  
  76.         printf("%lld\n",CountTotalPairs(arr,n));  
  77.         free(arr);  
  78.         arr = NULL;  
  79.     }  
  80. return 0;  
  81. }  

/**************************************************************

Problem: 1348

User: mmc_maodun

Language: C

Result: Accepted

Time:100 ms

Memory:1696 kb

****************************************************************/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

服务网格 Pattern: Service Mesh

自从几十年前首次引入以来,我们了解到分布式系统能够实现我们之前甚至无法思考的用例,但它们也会引入各种新问题。

14420
来自专栏数据库新发现

思科CEO钱伯斯:我非常尊敬华为

--------------------------------------------------------------------------------...

31810
来自专栏数据库新发现

第十三届搞笑诺贝尔奖(IgNobel)新鲜出炉

第十三届搞笑诺贝尔奖(IgNobel)新鲜出炉 中广网 10月04日 09:48

19030
来自专栏黄成甲

怎样科学地和人相处?

按照约定俗成的说法,一般跟人打交道有两个规则,一个是“黄金法则”,一个是“白银法则”。黄金法则并不适合现代社会对陌生人使用。因为你觉得好的东西别人不一定觉得好。...

15920
来自专栏知道一点点

20种新颖的按钮风格和效果【附源码】

Codrops 给我们分享了一组新鲜的按钮样式和效果的集合。它们中的大部分效果都使用了 CSS3 过渡和伪元素,他们都有一个共同点,那就是都具有简单性,没有太多...

16710
来自专栏计算机编程

2018-03-14 致敬霍金

  在黑洞领域,没有人知道这个怪兽是个什么东西,自从霍金给出“霍金辐射”与“奇点定理”过后,人们终于逐渐揭开了这宇宙中最为神秘的天体。在这里再次缅怀一下虽然坐着...

15220
来自专栏Leetcode名企之路

【Leetcode】59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

15930
来自专栏進无尽的文章

益思维-早期苹果员工胸牌背面写的11条“成功法则”

早期苹果员工胸牌背面写的11条“成功法则”这个胸牌的背面写着11条成功法则,其中每一条文字都充满了正能量。从中我们可以看到一些触动人心的感觉。

9520
来自专栏進无尽的文章

什么才是优秀的网站用户界面设计

16420
来自专栏黄成甲

怎样成为解决问题的高手(连载一)

什么是问题?一言以蔽之,问题来源于现实与目标的差距。因此,问题产生的原因可能是不清楚目标是什么;还可能是不知道差距产生的原因是什么;或者虽然知道差距产生的原因,...

35140

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励