- 难度: 困难
- 考察: 数组
- 来源: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
- 题解: https://mp.weixin.qq.com/s/FBlH7o-ssj_iMEPLcvsY2w
题目
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例1:
1 | nums1 = [1, 3] |
示例2:
1 | nums1 = [1, 2] |
思路
题目说的是给两个排好序的数组,让你求出这两个数组中所有元素按从小到大排列,排在中间的元素,时间复杂度也是有要求的,O(log(m + n)),m 和 n 分别是这两个数组的长度。
这里提到了时间复杂度为 O(log(m+n)) ,很容易想到的就是二分查找,所以现在要做的就是在两个排序数组中进行二分查找。
具体思路如下,将问题 转化为在两个数组中找第 K 个小的数 。
求中位数,其实就是求第 k 小数的一种特殊情况。
首先在两个数组中分别找出第 k/2 大的数,再比较这两个第 k/2 大的数,这里假设两个数组为 A ,B。
那么比较结果会有下面几种情况:
A[k/2] = B[k/2],那么第 k 大的数就是 A[k/2]
A[k/2] > B[k/2],那么第 k 大的数肯定在 A[0:k/2+1] 和 B[k/2:] 中,这样就将原来的所有数的总和减少到一半了,再在这个范围里面找第 k/2 大的数即可,这样也达到了二分查找的区别了。
A[k/2] < B[k/2],那么第 k 大的数肯定在 B[0:k/2+1]和 A[k/2:] 中,同理在这个范围找第 k/2 大的数就可以了。
关键点
二分查找
复杂度
- 时间复杂度:O(log(m + n))
时间复杂度:每进行一次循环,减少 k/2 个元素,所以时间复杂度是 O(log(k),而 k = (m+n) / 2,所以最终的复杂也就是 O(log(m+n)。
- 空间复杂度:O(1)
虽然用到了递归,但是可以看到这个递归属于尾递归,所以编译器不需要不停地堆栈,所以空间复杂度为 O(1)。
代码
递归去掉不需要的部分
1 | func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { |
笨办法,每次循环去掉不需要的部分
1 | func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { |