春招打卡第04篇——寻找两个正序数组的中位数-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。题目来源

二、思路分析

我的思考过程

求的是中位数，我首先考虑的就是要判断两种情况，奇数和偶数。

两个正序数组，两个数组的长度也已知，总长度用 size 表示，则中位数：

如果是奇数，则中位数是 size/2（代表下标）或 size/2 + 1（代表第几位）
如果是偶数，则中位数是 size/2 - 1 + size/2（代表下标）或 size/2 + size/2 + 1（代表第几位）

代码步骤应该是这样的：

首先需要有一个变量 order 来保存已经取出了多少数

先判断长度是奇数还是偶数，这将决定是会取出一个数还是取出两个数。

然后不断的从两个数组中取出数（须确保取出的数应该是正序的），然后令 order++，此时就可以对 order 进行判断是否是中位数。此处需要注意：如果下标自增和 order++ 一起，则后面取出中位数时，需要让下标减1；如果下标是在取出中位数后才自增，则可以直接使用下标。

需要思考的就是如何不断的从两个数组中正序的取出数：

使用两个指针（下标变量），先取出 A 数组的数和 B 数组的数，然后将两个数比较，取出较小的那个数，并且将数组的指针加一，然后继续比较，重复此过程。此处需要注意的就是对 下标越界 的判断！

遇到的问题

==42==ERROR: AddressSanitizer: heap-buffer-overflow on address

问题代码出在这里：

while (1) {
    if (nums1[i1] < nums2[i2]) {
        ...
        i1++;
    }
}
复制代码

i1++ 时，没有考虑到后面会直接使用该变量去寻址，所以当 i1 大于等于 nums1Size 的时候时，就会报错越界的错误，解决方式就是在使用 nums1[i1] 的时候需要先判断一下：

if (i1 < nums1Size && nums1[i1] < nums2[i2]) {...}
复制代码

输入是 [0,0] 和 [0,0] 是报错 ==42==ERROR

没有考虑到两个数组是完全相同的情况，解决方法很简单，就是给第一个判断条件宽松一点，因为前面已经有一个较严格的条件 i1 < nums1Size 。不然的话，程序只会从第二个数组中取出数组，从而导致再一次越界。

if (i1 < nums1Size && nums1[i1] <  nums2[i2])  // 错误代码
if (i1 < nums1Size && nums1[i1] <= nums2[i2])  // 正确代码
复制代码

输入是 [] 和 [1] 报错： ==43==ERROR: AddressSanitizer: heap-buffer-overflow on address

没有考虑到其中一个数组会为空的情况，故后面进行判断时，对一个空数组进行取值肯定会导致越界。解决方式是在前面进行一次判断

if (nums1Size == 0) {
    if (size % 2) {
        return nums2[mid];
    } else {
        return ((double)nums2[mid-1] + nums2[(mid)]) / 2;
    }
} else if (nums2Size == 0) {
    return size % 2 
        ? nums1[mid]
        : ((double)nums1[mid-1] + nums1[(mid)]) / 2
        ;
}
复制代码

输入 [100001] 和 [100000] 时报错：==42==

前面修改的考虑不全面，现在我需要记住这么一个原则：只要是有在调用数组，那么都必须对他们的下标进行越界判断。（解决完这个 bug 后终于 AC 了）

if (                     i1 < nums1Size && nums1[i1] <= nums2[i2]  ) // 错误代码
if ( i2 >= nums2Size || (i1 < nums1Size && nums1[i1] <= nums2[i2]) ) // 正确代码
复制代码

三、AC 代码

按照一开始的思路，不断修改终于 AC 的代码

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int i1 = 0;
    int i2 = 0;
    int order = 0;
    int size = nums1Size + nums2Size;
    int mid = size / 2;
    double result = 0;

    if (nums1Size == 0) {
        if (size % 2) {
            return nums2[mid];
        } else {
            return ((double)nums2[mid-1] + nums2[(mid)]) / 2;
        }
    } else if (nums2Size == 0) {
        return size % 2 
            ? nums1[mid]
            : ((double)nums1[mid-1] + nums1[(mid)]) / 2
            ;
    }

    if (size % 2) { // 奇
        while (1) {
            if (i2 >= nums2Size || (i1 < nums1Size && nums1[i1] <= nums2[i2])) {
                order++;
                if (order == mid+1) {
                    result = nums1[i1];
                    break;
                }
                i1++;
            } else {
                order++;
                if (order == mid+1) {
                    result = nums2[i2];
                    break;
                }
                i2++;
            }
        }
    } else {
        while (1) {
            if (i2 >= nums2Size || (i1 < nums1Size && nums1[i1] <= nums2[i2])) {
                order++;
                if (order == mid) {
                    result = nums1[i1] / 2.0;
                } else if(order == mid+1) {
                    result += nums1[i1] / 2.0;
                    break;
                }
                i1++;
            } else {
                order++;
                if (order == mid) {
                    result = nums2[i2] / 2.0;
                } else if(order == mid+1) {
                    result += nums2[i2] / 2.0;
                    break;
                }
                i2++;
            }
        }
    }

    return result;
}
复制代码