第四题：Median of Two Sorted Arrays

偏执的太偏执、 2022-08-06 20:29 128阅读 0赞

题目链接：[题目链接][Link 1]

题意：两个排好序的数组，找到中位数，如果是奇数好办，如果是偶数找到最中间的两个求平均值。

这一题的本质其实就是第mid小的数。

这一题看到一种好的方法，我们令k=mid，对于两个数组，分别取前k/2数，如果A\[k/2-1\]比B\[k/2-1\]大，那么说明B前k/2数肯定在k小数中，A的则不一定，则下面需要从A，B+k/2再次去寻找。。。反之对于B大的情况也是一样的，如果相等，那就是这两个数(相等)了，随便返回一个都OK。(Ps：解释一些为什么是k/2-1，因为k是从1开始取，数组下标从0开始)。

代码如下：

class Solution {
    public:
        // 参数K：从1开始
        //
        double dooo(int A[], int m, int B[], int n, int k){
            // 为了方便处理，默认m比n小
            //
            if (m > n)
                return dooo(B, n, A, m, k);
    
            // 如果数组A没有元素了，那么返回B中k-1就OK
            //
            if (!m)
                return B[k-1];
    
    		if (k==1)
    			return min(A[0], B[0]);
    
            // A中前面k/2数，如果比m大，那么取m
            // 对于b，那么和a_idx和是k
            //
            int a_idx = min(k/2, m);
            int b_idx = k - a_idx;
    
            // 如果A比B值大，说明B中前b_idx数都在K小数中
            // 反之一样
            //
            if (A[a_idx-1] > B[b_idx-1])
                // 如果B前b_idx数都在前k小数中，那么下面从A和B+b_idx再次进行递归
                //
                return dooo(A, m, B+b_idx, n-b_idx, k-b_idx);
            else if (A[a_idx-1] < B[b_idx-1])
                return dooo(A+a_idx, m-a_idx, B, n, k-a_idx);
            else
                return A[a_idx-1];
        }
    
        double findMedianSortedArrays(int A[], int m, int B[], int n) {
            // 如果是偶数，需要返回中间两个数，获得平均数
            // 注意第三个参数k从1开始，所以需要+1
            //
            if ((n + m) % 2 == 0)
                return (dooo(A, m, B, n, (m+n)/2) + dooo(A, m, B, n, (m+n)/2+1)) / 2.0;
            else
                // 否则中间数就OK
                return dooo(A, m, B, n, (m+n)/2+1);
        }
    };

[Link 1]: https://oj.leetcode.com/problems/median-of-two-sorted-arrays/