# LeetCode：4_Median of Two Sorted Arrays | 求两个排序数组的中位数 | Hard

```There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Subscribe to see which companies asked this question```

我自己想的方法，先排序在查找。两个数组，首先想到是归并排序，然后再查找两个数组合并之后的中间元素即为中位数。我们分析下时间复杂度主要用在了归并排序上，为O((m+n)log(m+n))，显然不符合题目要求。题目要求是O(log(m+n))，但是我将这个方法的代码提交上去，仍然通过了，说明LeetCode的编译平台并没有严格按照ACM OJ这种要求来设置。排序后查找的代码如下所示：

``` 1 //方法一：归并排序后查找：O((m+n)lg(m+n))，奇怪竟然通过了
2 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
3 {
4     size_t n1 = nums1.size(), n2 = nums2.size();
5     size_t n = n1+n2;
6     vector<int> nums(n,0);
7
8     assert(n > 0);
9
10     nums1.push_back(INT_MAX);
11     nums2.push_back(INT_MAX);
12
13     size_t i = 0, j = 0, k = 0;
14     while(i < n1 || j < n2) {
15         if (nums1[i] <= nums2[j]) {
16             nums[k++] = nums1[i++];
17         }
18         else
19             nums[k++] = nums2[j++];
20     }
21
22     return ((n%2) ? (double)nums[(n-1)/2]:(double)(nums[(n-1)/2]+nums[n/2])/2);
23 }```

``` 1 //方法二：二分法：O(lg(m+n)),满足题目要求
2 //get the kth number of two sorted array
3 double findkth(vector<int>::iterator a,int m,
4                vector<int>::iterator b,int n,
5                int k)
6 {
7     if(m >  n)
8         return findkth(b,n,a,m,k);
9     if(m == 0)
10         return b[k-1];
11     if(k == 1)
12         return min(*a,*b);
13
14     int pa = min(k/2,m),pb = k - pa;
15     if(*(a + pa - 1) < *(b + pb -1))
16         return findkth(a+pa,m-pa,b,n,k-pa);
17     else if(*(a + pa -1) > *(b + pb -1))
18         return findkth(a,m,b+pb,n-pb,k-pb);
19     else
20         return *(a+pa-1);
21 }
22
23 double findMedianSortedArrays1(vector<int>& nums1, vector<int>& nums2) {
24     vector<int>::iterator a = nums1.begin();
25     vector<int>::iterator b = nums2.begin();
26     int total = nums1.size() + nums2.size();
27
28     // judge the total num of two arrays is odd or even
29     if(total & 0x1)
30         return findkth(a,nums1.size(),b,nums2.size(),total/2+1);
31     else
32         return (findkth(a,nums1.size(),b,nums2.size(),total/2) + findkth(a,nums1.size(),b,nums2.size(),total/2 + 1))/2;
33 }```

0 条评论

• ### 大神洗礼第一讲——防御性编程相关

Author：bakari           Date:2012.10.18 这段时间非常有幸能够跟着一个非常牛的学长学习编程，现将每次学到的内容作为整理，方...

• ### 全排列（含递归和非递归的解法）

全排列在近几年各大网络公司的笔试中出现的比较频繁 首先来看看题目是如何要求的。 用C++写一个函数, 如 Foo(const char *str), 打印出 s...

• ### 算法导论2-9章补充几道题

本篇博文意在对前几章中遗漏的，本人觉得有意思的习题当独拿出来练练手。 1、习题2-4，求逆序对，时间复杂度要求Θ(nlgn) 定义：对于一个有n个不同的数组A,...

• ### LeetCode 349. Intersection of Two Arrays题目代码代码

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].

• ### LeetCode100|两个数组的交集II

这是自己目前输出的leetcode第100篇题解慢一点，才能更快，98道leetcode，也是自己坚持过程中一个结果，感谢周围的人和自己，这里道一句谢谢吧，没有...

• ### 【leetcode刷题】T43-两个数组的交集

Given two arrays, write a function to compute their intersection.

• ### 第K小数——折半删除

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

• ### 【LeetCode】88. 合并两个有序数组 双指针

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

• ### Array - 88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one s...