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

#include <climits>
#include <vector>
class Solution {
  public:

    int getKElement(vector<int> nums1, vector<int> nums2, int k) {
        int i = 0, j = 0;
        int n = nums1.size(), m = nums2.size();
        int res;
        while (i + j < k) {
            if (i < n && j < m) {
                if (nums1[i] < nums2[j]) {
                    res = nums1[i++];
                } else if (nums1[i] > nums2[j]) {
                    res = nums2[j++];
                }
            } else if (j < m) {
                res = nums2[j++];
            } else {
                res = nums1[i++];
            }

        }
        return res;
    }
    int getKthElement(vector<int> &nums1, int i, vector<int> nums2, int j, int k) {
        if (i >= nums1.size()) return nums2[j + k - 1];
        if (j >= nums2.size()) return nums1[i + k - 1];


        if (k == 1) return min(nums1[i], nums2[j]);

        int mid1 = i + k/2 - 1 < nums1.size() ? nums1[i + k/2 - 1] : INT_MAX;
        int mid2 = j + k/2 - 1 < nums2.size() ? nums2[j + k/2 - 1] : INT_MAX;

        if (mid1 < mid2) {
            return getKthElement(nums1, i + k/2, nums2, j, k-k/2);
        } else {
            return getKthElement(nums1, i, nums2, j + k/2, k-k/2);
        }
    }
  
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums1 int整型vector
     * @param nums2 int整型vector
     * @return double浮点型
     */
    double Median(vector<int>& nums1, vector<int>& nums2) {
        // write code here
        int n = nums1.size(), m = nums2.size();
        int mid;
        double res;
        if ((m + n) % 2 == 0) {
            mid = (m + n) / 2;
            res = (getKthElement(nums1, 0, nums2, 0, mid) + getKthElement(nums1, 0, nums2, 0, mid + 1)) / 2.0;
        } else {
            mid = (m + n) / 2 + 1;
            res =  getKthElement(nums1, 0, nums2, 0, mid) / 1.0;
        }
        return res;
    }
};