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 解题思路:   我自己想的方法,先排序在查找。

题目:

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 }

  

  看了下本题的难度系数,属于Hard级别的,说明本题不是那么容易对付的,又看了一下本题的Tag,其中罗列了两个重要的Tag:Divide and Conquer和Binary Search,说明本题需要用到两个方法:分治法和二分查找法,看了讨论里面,发现一种方法是这样的:求有序数组A和B有序合并之后第k小的数!如果A[k/2-1]<B[k/2-1],那么A[0]~A[k/2-1]一定在第k小的数的序列当中,可以用反证法证明。详细的思路请见这篇博文。代码如下:

 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
0
0
0
5
分享
相关文章
|
5月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
65 0
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
5月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
41 4
|
5月前
|
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
45 0
Leetcode第三十三题(搜索旋转排序数组)
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
5月前
|
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
100 0
|
5月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
35 0
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
7月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
82 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
166 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等