做题记录_(210130)

2021-01-30

2021/01/30做题记录

今天做的数组第四题，老规矩我们先看一下题;

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

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

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

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

示例 3：
1
2
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
1
2
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
1
2
输入：nums1 = [2], nums2 = []
输出：2.00000
这道题我认为还是比较简单的，个人思路如下：

因为题中已指定两个正序数组，现将 nums1 和 nums2 进行合并排序，之后在合并的数组中寻找中位数即可，代码如下：

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int resSize = nums1Size + nums2Size;    //目标数组的长度
    int* res = malloc(sizeof(int) * resSize);
    int i = 0;     //nums1的数组指针
    int j = 0;     //nums2的数组指针
    int k = 0;     //res的数组指针
    while(i<nums1Size&&j<nums2Size)     //合并排序
    {
        if(nums1[i]<=nums2[j])
            res[k++] = nums1[i++];
        else
            res[k++] = nums2[j++];
    }
    while(i<nums1Size)                  //顺序填入nums1
        res[k++] = nums1[i++];
    while(j<nums2Size)                  //顺序填入nums2
        res[k++] = nums2[j++];
    if(resSize % 2==0)
        return ((double)(res[resSize/2 - 1] + (double)res[resSize/2])/2);
    else
        return ((double)res[resSize/2]);
}

经分析时间复杂度为O(m+n)，具体怎么实现O(log (m+n)) ，留着以后回头再想吧 ······

不过初步分析，如果使用二分法，时间复杂度应该能满足要求。