题解 | #两个升序数组的中位数#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums1 int整型vector
     * @param nums2 int整型vector
     * @return double浮点型
     */
    double Median(vector<int>& nums1, vector<int>& nums2) {
        // write code here
        // 前面做过在两个长度相等的排序数组中找到上中位数，和这道题是类似的
        // 现在这道题和之前不一样的点在于两个数组长度不一样，然后必须找中位数
        // 长度不一样好解决，还是先计算中位数排多少位，设置 cut1 和 cut2，二分去找就行
        // 现在要找中位数，这里就要分一下总共元素个数的奇偶，偶数的话找上中位数和下中位数，再平均即可
        if (nums1.size() > nums2.size()) {
            swap(nums1, nums2);
        }

        // 注意这里把较短的数组放前面，且设短数组长度为 m，长数组长度为 n
        int m = nums1.size();
        int n = nums2.size();
        int totalLeft = (m + n + 1) /
                        2; // 多加 1 保证总数为奇数个时取到中间

        int left = 0;
        int right = m;

        while (left < right) {
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;
            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                left = i;
            }
        }

        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? INT_MIN : nums1[i - 1];
        int nums2LeftMax = j == 0 ? INT_MIN : nums2[j - 1];
        int nums1RightMin = i == m ? INT_MAX : nums1[i];
        int nums2RightMin = j == n ? INT_MAX : nums2[j];

        if ((m + n) % 2 == 1) {
            return max(nums1LeftMax, nums2LeftMax);
        } else {
            return (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin,
                    nums2RightMin)) / 2.0;
        }
    }
};

这道题最抽象的地方在于 C++ 是通过不了自测样例的，和函数返回值类型有关，而 C++ 里返回的 double 类型的结果会有一堆 0 放在最后，比如题目期望的是 3.5，我们的代码返回的结果是 3.5000 这样的情况。