题目链接:
力扣leetcode-cn.com
题目描述:
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数&＃xff0c;并且要求算法的时间复杂度为 O(log(m &＃43; n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例:
示例 1:
nums1 &＃61; [1, 3]
nums2 &＃61; [2]则中位数是 2.0
示例 2:
nums1 &＃61; [1, 2]
nums2 &＃61; [3, 4]则中位数是 (2 &＃43; 3)/2 &＃61; 2.5
思路:
这道题如果时间复杂度没有限定在
![]()
,我们可以用
![]()
的算法解决,用两个指针分别指向两个数组,比较指针下的元素大小,一共移动次数为
(m&＃43;n &＃43; 1)/2,便是中位数.
首先,我们理解到底什么是中位数,指的是该数左右两边数字的个数相等.
比如: odd : [1,| 2 |,3],2就是这个数组的中位数,左右两边都只要1位;
even: [1,| 2, 3 |,4],2,3就是这个数组的中位数,左右两边1位;
那么,现在我们有两个数组:
num1: [a1,a2,a3,...an]
nums2: [b1,b2,b3,...bn]
[nums1[:left1],nums2[:left2] | nums1[left1:], nums2[left2:]]
只要保证左右两边个数相同,中位数就在|这个边界旁边产生.
如何找边界值,我们可以用二分法,我们先确定num1取m1左半边,那么num2取m2 &＃61; (m&＃43;n&＃43;1)/2 - m1的左半边,找到合适的m1,就用二分法找,关于我的二分法总结,见另一篇文章.
当 [ [a1],[b1,b2,b3] | [a2,..an],[b4,...bn] ]
我们只需要比较 b3和a2的关系的大小,就可以知道这种分法是不是准确的!
例如:我们令:
nums1 &＃61; [-1,1,3,5,7,9]
nums2 &＃61;[2,4,6,8,10,12,14,16]
当m1 &＃61; 4,m2 &＃61; 3
median &＃61; (num1[m1] &＃43; num2[m2])/2
时间复杂度:
对于代码中边界情况,大家需要自己琢磨.
感觉对自己有用,就点个赞吧,并关注我的知乎专栏,嘻嘻!
代码:
python版
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:n1 &＃61; len(nums1)n2 &＃61; len(nums2)if n1 > n2:return self.findMedianSortedArrays(nums2,nums1)k &＃61; (n1 &＃43; n2 &＃43; 1)//2left &＃61; 0right &＃61; n1while left 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )if (n1 &＃43; n2) % 2 &＃61;&＃61; 1:return c1c2 &＃61; min(nums1[m1] if m1
c&＃43;&＃43;版
class Solution {
public:double findMedianSortedArrays(vector& nums1, vector& nums2) {const int n1 &＃61; nums1.size();const int n2 &＃61; nums2.size();if(n1>n2) return findMedianSortedArrays(nums2, nums1);const int k &＃61; (n1 &＃43; n2 &＃43; 1)/2;int left &＃61; 0;int right &＃61; n1;while(left &＃61; n1 ? INT_MAX: nums1[m1],m2 >&＃61; n2 ? INT_MAX : nums2[m2]);return (c1 &＃43; c2) * 0.5;}
};
java版
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n1 &＃61; nums1.length;int n2 &＃61; nums2.length;if (n1>n2)return findMedianSortedArrays(nums2, nums1);int k &＃61; (n1 &＃43; n2 &＃43; 1)/2;int left &＃61; 0;int right &＃61; n1;while(left &＃61; n1 ? Integer.MAX_VALUE :nums1[m1],m2 >&＃61; n2 ? Integer.MAX_VALUE : nums2[m2]);return (c1 &＃43; c2) * 0.5;}
}
同步更新博客:
一起刷LeetCode - 威行天下 - 博客园www.cnblogs.com
京公网安备 11010802041100号