Median of Two Sorted Arrays——算法课上经典的二分和分治算法

看到这道题的通过率很诧异,感觉这道题挺容易的,因为其实它的思想还是很简单的。

1)最笨的方法去实现,利用排序将两个数组合并成一个数组,然后返回中位数,这种方法应该会超时。

2)利用类似merge的操作找到中位数,利用两个分别指向A和B数组头的指针去遍历数组,然后统计元素个数,直到找到中位数,此时算法复杂度为O(n)。

我一开始想到的就是2)这种方法,但是真正的写起代码来,才发现有很多的细节需要去考虑,挺繁琐的。

我们仅需要第k大的元素,不需要排序这个复杂的操作:可以定义一个计数器m,表示找到了第m大的元素;同时指针pa,pb分别指向数组A,B的第一个元素,使用merge-sort的方式,当A的当前元素小于B的当前元素时:pa++, m++,当*pb < *pa时,pb++, m++。最终当m等于k时,就得到了第k大的元素。时间复杂度O(k),但是当k接近于m+n时,复杂度还是O(m+n);

3)

从题目中的要求O(log(m+n))可以联想到肯定要用到二分查找的思想

那么有没有更好的方案?我们可以考虑从k入手。如果我们每次能够删除一个一定处于第k大元素之前的元素,那么需要进行k次。但是如果我们每次都能删除一半呢?可以利用A,B有序的信息,类似二分查找,也是充分利用有序。 
假设A 和B 的元素个数都大于k/2,我们将A 的第k/2 个元素(即A[k/2-1])和B 的第k/2个元素(即B[k/2-1])进行比较,有以下三种情况(为了简化这里先假设k 为偶数,所得到的结论对于k 是奇数也是成立的): 
- A[k/2 - 1] == B[k/2 - 1];    

(就是这里感觉不太明白,如果k==3,感觉怎么凑都不对啊!!!!!)

解释:这里可能有人会有疑问,如果k为奇数,则m不是中位数。这里是进行了理想化考虑,在实际代码中略有不同,是先求k/2,然后利用k-k/2获得另一个数。
- A[k/2 - 1] > B[k/2 - 1]; 
- A[k/2 - 1] < B[k/2 - 1]; 
如果A[k/2 - 1] < B[k/2 - 1] ,意味着 A[0] 到 A[k/2 - 1] 的元素一定小于 A+B 第k大的元素。因此可以放心的删除A数组中的这k/2个元素; 
同理,A[k/2 - 1] > B[k/2 - 1];可以删除B数组中的k/2个元素; 
当A[k/2 - 1] == B[k/2 - 1] 时,说明找到了第k大的元素,直接返回A[k/2 - 1] 或B[k/2 - 1]的值。

因此可以写一个递归实现,递归终止条件是什么呢? 
- A或B为空时,直接返回A[k-1] 或 B[k-1] 
- 当k = 1时,返回min(A[0], B[0]) //第1小表示第一个元素 
- 当A[k/2 - 1] == B[k/2 - 1] 时,返回A[k/2 - 1] 或B[k/2 - 1]

我们可以看出,代码非常简洁,而且效率也很高。在最好情况下,每次都有k一半的元素被删除,所以算法复杂度为logk,由于求中位数时k为(m+n)/2,所以算法复杂度为log(m+n)。 

转自:http://www.bubuko.com/infodetail-797383.html

最终实现的代码为(代码是直接拷贝的别人的,到时候还需要自己写一下):

    static int find_kth(int* A, int m,int* B, int n, int k);
    static int min(p, q) {return (p < q) ? p : q;}
    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
        int m = nums1Size;
        int n = nums2Size;
        int total = m+n;
        int k = total/2;
        if(total & 0x01) {   //这里用total%2==1也行
            return find_kth(nums1, m, nums2, n, k+1); //奇数,返回唯一中间值
        } else {
            return (find_kth(nums1, m, nums2, n, k) + find_kth(nums1, m, nums2, n, k+1)) / 2.0; //偶数,返回中间2个的平均值
        }
    }
    //找到A,B组合中第k小的值: AB[k-1]
    int find_kth(int* A, int m,int* B, int n, int k) {
        //假设m都小于n
        if (m > n)
            return find_kth(B, n, A, m, k);
        if (m == 0)
            return B[k-1];
        if (k == 1) //终止条件
            return min(A[0], B[0]);

        int i_a = min(m, k/2);    //这两步的意义就是之前解释的遇到奇数时的情况
        int i_b = k - i_a;

        if (A[i_a-1] < B[i_b-1])
            return find_kth(A+i_a, m-i_a, B, n, k-i_a);
        else if (A[i_a-1] > B[i_b-1])
            return find_kth(A, m, B+i_b, n-i_b, k-i_b);
        else
            return A[i_a-1];
    }

  下面是我更改的C++的版:

class Solution {
public:
    int findk(vector<int>& nums1,int len1, vector<int>& nums2,int len2,int k)
    {
        
        if(len1>len2)
            return findk(nums2,len2,nums1,len1,k);
        if(len1==0)
            return nums2[k-1];
        if(k==1)
            return min(nums1[0],nums2[0]);
        int flag1=min(len1,k/2);
        int flag2=k-flag1;
        if(nums1[flag1-1]<nums2[flag2-1])
        {
            vector<int> temp(nums1.begin()+flag1,nums1.end());
            return findk(temp,len1-flag1,nums2,len2,k-flag1); 
        }
        else if(nums1[flag1-1]>nums2[flag2-1])
        {
            vector<int> temp(nums2.begin()+flag2,nums2.end());
            return findk(nums1,len1,temp,len2-flag2,k-flag2);
        }
            
        else
            return nums1[flag1-1];
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1=nums1.size();
        int len2=nums2.size();
        int k=(len1+len2)/2;
        if((len1+len2)%2==1)
            return findk(nums1,len1,nums2,len2,k+1);
        else
            return (findk(nums1,len1,nums2,len2,k)+findk(nums1,len1,nums2,len2,k+1))/2.0;
    }
};

  

更多相关文章
  • 据英国路透社5月12日报道,美国电动汽车生产商特斯拉汽车(Tesla)称,在全球最大汽车市场--中国的电动汽车充电标准设立后,将改装面向中国市场生产的新电动汽车,以符合新标准.特斯拉11日在其网站上发布的声明称,该公司也在积极参与中国电动汽车充电标准的制定.由于未完成在中国的销售目标,该公司今年早些 ...
  • 接css3选择器(一) 八.结构性伪类选择器[:nth-child(n)] :nth-child(n)选择器用来匹配某个父元素的一个或多个特定的子元素,和jquery中一样. 其中"n"是其参数,而且可以是整数值(1,2,3,4),也可以是表达式(2n+1,-n+5)和关键字(o ...
  • 1, Buffer cache的作用 为了提高磁盘设备的IO性能,我们采用内存作为磁盘设备的cache.用户操作磁盘设备的时候,首先将数据写入内存,然后再将内存中的脏数据定时刷新到磁盘.这个用作磁盘数据缓存的内存就是所谓的buffer cache.在以前的Linux系统中,有很完善的buffer c ...
  • 最近在和小伙伴讨论如何高效的编写css代码的问题,于是我们想到了使用css的预处理语言.例如(less,sass等).最后我们决定使用less(相对于其他css预处理语言更简单,语法更接近css).   先说说什么是less? 简单的说,你可以在你的css文件中使用变量.函数等方式来编写你的css. ...
  • 1.Fragment的添加方式 FragmentTransaction ft = getFragmentManager().beginTransaction(); ft.hide ft.show ft.add ft.replace ft.hideft.showa.let the old fragme ...
  • JAVA解析XML之SAX方式 SAX解析xml步骤 通过SAXParseFactory的静态newInstance()方法获取SAXParserFactory实例factory 通过SAXParserFactory实例的newSAXParser()方法返回SAXParser实例parser 创建一 ...
一周排行
  • 为什么翻译类计算机图书的质量这样差   一.翻译类技术图书的现状 就IT领域而言,我们自己拥有独立知识产权的东西太少,而且技术发展也相对滞后(这是有因果关系的),这是不可否认的事实.但是自从互联网在中国出现以来,这种 ...
  • 长江商报消息 昨日,有消息称,苹果在即将于9月12日出品的新机型"iPhone5"中换掉了大部分三星生产的零件,除了电池外,屏幕也悄然换成了其他厂商.作为零件订单中的"老搭档" ...
  • 一.在Vmware Workstatioin上安装ESXi 1.安装的必要条件 运行VMware Workstatioin的机器必须拥有64比特的CPU,而CPU也必须支持VT-X技术 2.安装ESXi 1)新建虚拟 ...
  •         在dbsnake 上看到的这篇文章,转过来. 主要还是学习解决问题的一个思路.这个往往比问题的解决更重要.        原文链接如下:       http://dbsnake.com/2010/0 ...
  • 这段时间,不管是分析师还是投资者似乎都在为苹果的未来伤脑筋.但苹果却不这么认为."我们要做智能手机的领导者,对市场份额不是特别关心."就在前几天,苹果全球高级副总裁菲利普·席勒到访中国时表达了这样 ...
  • 在nginx的配置文件中加上  location ~ \.(jpg|png|jpeg|bmp|gif|swf|css)$         {             access_log off;           ...
  • 1 加入东软 2013年的春天加入了东软,当初决定来到东软也是因为一个东软好友的推荐,外加当时一个项目的机会.这些年经历过了对日.欧美以及国内项目,我还是更喜欢国内项目:个人的发挥的空间最大,项目能主导的东西最多. ...
  •  网站系统的伸缩性架构最重要的技术手段就是使用服务器集群功能,通过不断地向集群中添加服务器来增强整个集群的处理能力.“伸”即网站的规模和服务器的规模总是在不断扩大. 1.网站架构的伸缩性设计 网站的伸缩性设计可以分成 ...
  • 今天小编为大家带来了魔兽世界6.1武器战输出手法 wow6.1武器战属性天赋详解,感兴趣的朋友们可以跟着小编去下文了解一下哦. 为大家带来6.1版本的武器战士详尽攻略,喜欢玩这个天赋的朋友不要错过呦,内容相当丰富,慢 ...
  • 集群和负载均衡的概念 集群(Cluster) 所谓集群是指一组独立的计算机系统构成的一个松耦合的多处理器系统,它们之间通过网络实现进程间的通信.应用程序可以通过网络共享内存进行消息传送,实现分布式计算机. 负载均衡( ...