题解 | #在两个长度相等的排序数组中找到上中位数# 常见的归并法

class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    void merge(vector<int>& arr1, vector<int>& arr2, vector<int> &ret) {
        int len1 = arr1.size(), len2 = arr2.size();
        if (len1 == 0) {
            ret = arr2;
        }
        if (len2 == 0) {
            ret = arr1;
        }
        int arr1Index = 0, arr2Index = 0, retIndex = 0;
        
        while(arr1Index < len1 && arr2Index < len2) {
            if (arr1[arr1Index] < arr2[arr2Index]) {
                ret[retIndex++] = arr1[arr1Index++];
            } else {
                ret[retIndex++] = arr2[arr2Index++];
            }
        }
        
        if (arr1Index == len1) {
            for (int i = arr2Index; i < len2; i++) {
                ret[retIndex ++] = arr2[i];
            }
        } else {
            for (int i = arr1Index; i < len1; i++) {
                ret[retIndex ++] = arr1[i];
            }
        }
    }
    
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int len1= arr1.size(), len2 = arr2.size();
        vector<int> mergeArr(len1 + len2, 0);
        merge(arr1, arr2, mergeArr);
        int mid = (len1 + len2) / 2;
        return mergeArr[mid - 1];
    }
};