网页培训多少钱,网站建设制作设计seo优化湖北,软件工程专业就业方向及前景分析,wordpress 新编辑器更好的阅读体验#xff0c;请点击 YinKai s Blog。 题目#xff1a;寻找两个正序数组的中位数 给定两个大小分别为 m 和 n 的正序#xff08;从小到大#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
… 更好的阅读体验请点击 YinKai s Blog。 题目寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 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 提示 nums1.length m nums2.length n 0 m 1000 0 n 1000 1 m n 2000 -106 nums1[i], nums2[i] 106
来源力扣LeetCode
解题思路
1暴力
直接将两个数组合并然后进行排序直接算出中位数:
数组长度为奇数数组的中位数为a[len / 2]数组长度为偶数数组的中位数为(a[len / 2] a[len / 2 - 1]) / 2
这题的时间复杂度的上限在排序是O((n m)long(n m))显然没有达到题目的要求 但也勉强可以AC。
代码如下
class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {vectorint res;for (int i 0; i nums1.size(); i )res.push_back(nums1[i]);for (int i 0; i nums2.size(); i )res.push_back(nums2[i]);sort(res.begin(), res.end());int len res.size();if (len 1) {return res[len / 2];} else {return double((res[len / 2] res[len / 2 - 1]) / 2.0);}}
};
