LeetCode 4. 寻找两个正序数组的中位数

墨蓝 2023-01-01 08:59 139阅读 0赞

**上一篇博客：[LeetCode 605. 种花问题（简单模拟）——每日一题][LeetCode 605.]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 4. 寻找两个正序数组的中位数][LeetCode 4.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例 1
     *  示例 2
     *  示例 3
     *  示例 4
     *  示例 5
     *  提示：
 *  题解
 *   *  解题思路
     *  解题代码

# 题目信息 #

## 题目描述 ##

给定两个大小为 **m** 和 **n** 的正序（从小到大）数组 `nums1` 和 `nums2`。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 `O(log (m+n))` 的算法解决此问题吗？

## 示例 1 ##

> 输入：nums1 = \[1,3\], nums2 = \[2\]  
> 输出：2.00000  
> 解释：合并数组 = \[1,2,3\] ，中位数 2

## 示例 2 ##

> 输入：nums1 = \[1,2\], nums2 = \[3,4\]  
> 输出：2.50000  
> 解释：合并数组 = \[1,2,3,4\] ，中位数 (2 + 3) / 2 = 2.5

## 示例 3 ##

> 输入：nums1 = \[0,0\], nums2 = \[0,0\]  
> 输出：0.00000

## 示例 4 ##

> 输入：nums1 = \[\], nums2 = \[1\]  
> 输出：1.00000

## 示例 5 ##

> 输入：nums1 = \[2\], nums2 = \[\]  
> 输出：2.00000

## 提示： ##

*  nums1.length == m
 *  nums2.length == n
 *  0 <= m <= 1000
 *  0 <= n <= 1000
 *  1 <= m + n <= 2000
 *  \-106 <= nums1\[i\], nums2\[i\] <= 106

# 题解 #

## 解题思路 ##

首先使用 `归并排序` 将两个数组从小到大进行排序，并放到另一个 `vector` 数组 `ans` 中，然后再找到并计算出新数组的中间值。如果结果数组 `ans` 的长度为奇数那么中间值只有一个，此时直接返回 `double` 类型的中间值即可。如果 `ans` 的长度为偶数，那么中间值有两个，需要将两个中间值相加除以 **2** 之后再返回。有关归并排序的详细解释请看 [经典排序算法之归并排序详解][Link 1]。

## 解题代码 ##

class Solution { 
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 
            vector<int> ans;
            int len1 = nums1.size(), len2 = nums2.size();
    
            // 进行归并排序
            int i = 0, j = 0;
            while (i < len1 && j < len2) { 
                if (nums1[i] <= nums2[j]) ans.push_back(nums1[i++]);
                else ans.push_back(nums2[j++]);
            }
            while (i < len1) ans.push_back(nums1[i++]);
            while (j < len2) ans.push_back(nums2[j++]);
    
            // 计算并返回结果
            int len3 = ans.size();
            double res = 0;
            if (len3 % 2 != 0) res = (double)ans[len3 / 2];
            else res = (double)(ans[len3 / 2] + ans[(len3 / 2) - 1]) / 2;
            return res;
        }
    };

--------------------

> 未完待续，持续更新中……  
> ![在这里插入图片描述][2021010121252543.jpg]

[LeetCode 605.]: https://ac-fun.blog.csdn.net/article/details/112062054
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 4.]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[Link 1]: https://ac-fun.blog.csdn.net/article/details/107300891
[2021010121252543.jpg]: /images/20221120/bc48a0e2008547f0b4b7e25869965f19.png