[数据结构与算法][力扣题解]4. 寻找两个正序数组的中位数

[力扣题解]4. 寻找两个正序数组的中位数

题目描述：

解题结果：

解题思路： 采用将两个正序数组nums1和nums2合并的方法，在合并后的数组里找中位数。比较难的地方在于怎么把两个数组合并。具体思路是从nums1和nums2的最大一端开始，依次比较两个数组各自的最大元素哪个比较大，将比较大的那一个取出来放入合并后数组中，直到其中一个数组为空。比如nums1：1，3和nums2：2，4.首先比较两个数组最大的元素3和4，4比较大，将其取出放入合并后数组，于是nums2数组中元素2成为最大，将2与3进行比较，3比较大，将其取出放入合并后数组。
如果两个数组元素不等时，注意将剩余部分合并入结果。
具体代码：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int length;
        vector<int> result = Merge(nums1, nums2);
        length = result.size();
        if (length % 2 == 0) {
            return (result[length / 2] + result[length / 2 - 1]) / 2.0;
        }
        else {
            return result[length / 2];
        }
    }

    vector<int> Merge(vector<int> nums1, vector<int> nums2) {
        vector<int> result;
        int length, i;
        int e;
        while (!nums1.empty()&&!nums2.empty()) {
            if (nums1.back() > nums2.back()) {
                e = nums1.back();
                nums1.pop_back();
                result.push_back(e);
            }
            else {
                e = nums2.back();
                nums2.pop_back();
                result.push_back(e);
            }
            //cout << result.back();
        }
        if (nums1.empty()) {
            length = nums2.size();
            for (i = length - 1; i >= 0; i--) {
                result.push_back(nums2.back());
                nums2.pop_back();
            }
        }
        else {
            length = nums1.size();
            for (i = length - 1; i >= 0; i--) {
                result.push_back(nums1.back());
                nums1.pop_back();
            }
        }
        return result;
    }
};