Median of two sorted arrays
Median of two sorted arrays #hard
Given two sorted arrays nums1
and nums2
of size m
and n
respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n))
.
Example 1:
1 | Input: nums1 = [1,3], nums2 = [2] |
Example 2:
1 | Input: nums1 = [1,2], nums2 = [3,4] |
Example 3:
1 | Input: nums1 = [0,0], nums2 = [0,0] |
Example 4:
1 | Input: nums1 = [], nums2 = [1] |
Example 5:
1 | Input: nums1 = [2], nums2 = [] |
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
Solution:
- 如果brute force 我们直接 merge,得到median就 O(m+n). 看到题目要求 O(log(m+n)), 知道应该使用 binary search.
- ==考虑,如果我们在 array A 中找到一个index i,在 array B 中对应的 index j(median或median旁边),必须满足 i + j = (m + n + 1)/2. 而且,必须满足 A[i-1] < B[j] 且 B[j-1] < A[i]。==
- 如果 A[i-1] > B[j], 证明说 A[i] 会比真正 median 大,所以 i 减小;反之亦然。
总结起来就是这个图片:
![1_exp](median of two sorted arrays.assets/1_exp.png)
结合以上的点,我们选择在 array A 里面搜索,然后找到 对应的 array B 中的 index j, 之后接着判断。
==这里我们因为 j = (m+n+1)/2 - i 得到,保证 j >= 0, 所以需要 m <= n。而且也加快搜索速度!!!==
1 | def findMedianSortedArrays(self, A, B): |
==注意这里 i 的搜索范围是 [0,m] (0,m 都包括), 因为 i 类似于 cut,i=0 代表 A[0] 也在 right_part, i=m 代表 A[m-1] 在 left_part==
因为 (m+n+1)/2 保证了左边比右边长,所以如果奇数的话,max_of_left 就是 median
Comments