4 Median of Two Sorted Arrays
Last updated
Was this helpful?
Last updated
Was this helpful?
There are two sorted arrays nums1and 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)).
Example 1:
Example 2:
(1) Binary Search
Binary Search: 时间复杂度O(log(m + n)), 空间复杂度O(log(m + n)),因为递归
思路: 这题要我们求两个有序数组的合并后的中位数,其实就相当于找第k个数,其中k = (m + n)/2, m和n分别为两个数组的长度。我们可以利用二分的思想,缩小搜索的范围。做法是,分别对两个数组nums1和nums2找出各自前k/2个数,假设nums1的第k/2个数的位置是m, nums2的第k/2个数的位置是n, 如果nums1[m] < nums2[n], 说明nums1的前m个数肯定小于第k个数,所以抛弃num1的前k/2个数。这里用. 最后要注意一些边界条件处理