寻找两个正序数组的中位数

题目描述

  给定两个大小分别为m和n的正序(从小到大)数组nums1和nums2。要求找出这两个正序数组的中位数。

输入输出样例

  输入是两个数组，合并后的数组顺序是由小到大。

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000

  对于偶数个数字的数组，中位数是(n/2)。对于奇数个数字的数组，中位数为(n+(n+1))/2的值。

题解

  简单解法,就是将num2的值使用emplace_back()函数将nums2的接在nums1后面，之后再使用sort()。进行一个从小到大的排序，最后根据奇数偶数，返回不同的中位数。但是这个做法的缺点就是，使用sort后的时间复杂度就变为了$n * log^{2}(n)$,具体代码如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
       int n = nums1.size(),m = nums2.size();

       for (int i = 0; i < m ; i++) {
           nums1.emplace_back(nums2[i]);
       } 

       sort(nums1.begin(),nums1.end());

       int a = nums1.size();
       int k = a / 2;

       if (a % 2 == 1) {
           return nums1[k];
       }
       else
           return (double)(nums1[k-1]+nums1[k])/2;
    }
};