type
Post
status
Published
date
Oct 23, 2023
slug
summary
tags
category
leetcoder
icon
password
4. Median of Two Sorted Arrays
题目描述
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:
Example 2:
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
106 <= nums1[i], nums2[i] <= 106
题解:
1.自己的解法
纯暴力解法，寻求两个有序数组的中位数即先把两个有序数组合并，并用algorithm库里的sort函数将新数组排序并输出中位数。
但这似乎是不太符合折腾的，采用归并排序试试。
首先回忆（重学）归并排序基础代码
然后运用此思想，将两个有序数组做最后一次合并
但似乎在时间复杂度上O(m+n)不符合要求
O(log(m+n)。看到
log，很明显，我们只有用到二分的方法才能达到，还是得考虑边界问题和各式各样的递归啊
- Author:KIRITO
- URL:https://www.kirito.work/article/e06b2d64-629f-4d95-b1df-1b85b3ad7333
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
