描述
Given two sorted arrays nums1
and nums2
of size m
and n
respectively, return the median of the two sorted arrays.
Follow up: The overall run time complexity should be O(log (m+n))
.
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1]
Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = []
Output: 2.00000
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
解析
解析1:暴力解法。
因为知道两个数组的长度
- 如果两数组长度之和为偶数,则中位数为第(m+n+1)/2与(m+n+2)/2之和的二分之一
- 如果两数组长度之和为奇数,则中位数为第(m+n+1)/2个数
循环遍历两个数组,抛弃掉小的那一个数,前进直到找到想要的数。
时间复杂度O(n)
解析2:利用二分法思想
1 | class Solution { |
利用二分法的思想可以将时间复杂度降到O(log(m+n))
1 | double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) |
首先来看第一个函数,
m
代表nums1的大小n
代表nums2的大小left
表示中间两个元素的左边那个right
表示中间元素的右边那个(如果为数组和大小为奇数时,left
和right
是相等的)odd
用来判断数组大小之和是否为奇数
最后判断一下,如果是奇数的话,只需要调用一次函数,避免函数调用的开销。
关键点在第二个函数上
1 | int findKth(std::vector<int> &nums1, int i, std::vector<int> &nums2, int j, int k) |
i
表示,数组一从indexi
开始j
表示,数组二从indexj
开始k
表示,要寻找的元素在第k
位(从1开始算的第k位,不是index k)
1 | static int findKth(std::vector<int> &nums1, int i, std::vector<int> &nums2, int j, int k) |
这个函数就是去想要一个概念数组,里面的元素是排好序的nums1和nums2,目的是为了淘汰第k
位之前的元素以找到nums[k
]
退出条件
如果
i(j同理)
(数组的起始位置)都比数组的大小还大了,那么说明要找的元素一定不在nums1里面,则把nums1的所有元素淘汰掉,直接返回nums2从j
开始的第k
位元素。如果k==1的时候,表示从第
i
开始的第一个,只剩一个可以选择了,当然是选择两个之中小的一个 。
令midVal1
为数组1中间那个数,midVal2
为数组2中间那个数,那么每次可以淘汰掉前k/2个,例如midVal2比midVal1小的时候,数组2以j
开始的后k/2
个数据只能作为我们要找的概念数组的第k
个数据的垫脚石
当淘汰掉k/2后,需要找的元素就是index往后k/2后的第k/2个!
直到满足两个退出条件之一后退出即可
时间复杂度为O(log(m+n))
总结
这是一道很经典的题,思路也很新奇,在秋招的时候几个大厂出了这样的题,前几天面腾讯的时候面试官也问了。
记下来!