04.探求两个有序数组的中位数（难度：困难）

藏宝库编辑 · 2024-9-29 14:47:22

04.探求两个有序数组的中位数（难度：困难）

标题形貌

给定两个巨细为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，而且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]nums2 = [2]则中位数是 2.0示例 2:
nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5解法一：

这道题是求两个有序数组的中位数，假如不限定时间复杂度的话，那么这道题将会无比简朴。
把长度为m和长度为n的两个数组的数据放在一个新的数组中，然后对数组举行排序，找到中位数。
找中位数的时间，由于组合后的数组元素个数(m + n)的奇偶性不确定，假如是奇数的话，那么中位数就是第（m+n）/ 2 个元素，假如是偶数的话，那么中位数就是第（m + n ）/ 2 个元素和第（m + n）/ 2 + 1个。
我们可以使用int整型向下取整的特点，把上面两种环境归结为一种通用的解法，我们可以找到下标（m + n - 1）/ 2和下标（m + n ）/ 2元素，然后求两数的平均值。

04.探求两个有序数组的中位数（难度：困难）

所属分类: 问答交流

新帖推荐: 30日

推荐作品