4. Median of Two Sorted Arrays

 https://leetcode.com/problems/median-of-two-sorted-arrays/

4. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

 

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

思路：
比較差的做法是，使用額外的空間
把兩個 array merge 在一起，保持 sorted
如果兩個 array 都還有元素，就比大小，小的先 merge 進新 array
直到array 1 空了，就把 array 2 剩下的元素 merge 進新 array
最後回傳中位數

class Solution {

public:

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        vector<int> mergeArray;

        vector<int>::iterator it1 = nums1.begin();

        vector<int>::iterator it2 = nums2.begin();

        while(it1 != nums1.end()) {

            if (it2 != nums2.end()) {

                if (*it1 < *it2) {

                    mergeArray.push_back(*it1);

                    it1++;

                } else {

                    mergeArray.push_back(*it2);

                    it2++;

                }

            } else {

                mergeArray.push_back(*it1);

                it1++;

            }

        }

        // append rest of array 2

        while(it2 != nums2.end()) {

            mergeArray.push_back(*it2);

            it2++;

        }

        int mid = mergeArray.size() / 2;

        if (mergeArray.size() % 2 == 0) {

            return (double)(mergeArray[mid] + mergeArray[mid-1]) / 2;

        } else {

            return mergeArray[mid];

        }

    }

};

比較好的做法，不需要使用額外空間
因為你知道兩個 array 相加的元素個素 totalSize
所以可以知道中位數是在第幾個元素 half
就一路找出位在中位數的元素值就好 mid
要記得記住前一個元素值 preMid，因為若元素個素是偶素
那中位數就是 (preMid + mid) / 2

class Solution {

public:

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        vector<int> mergeArray;

        vector<int>::iterator it1 = nums1.begin();

        vector<int>::iterator it2 = nums2.begin();

        int totalSize = nums1.size() + nums2.size();

        int half = totalSize / 2;

        double mid = 0;

        int preMid = 0;

        while(half >= 0) {

            preMid = mid; // keep previous value of mid

            if (it1 != nums1.end() && it2 != nums2.end()) {

                if (*it1 < *it2) {

                    mid = *it1;

                    it1++;

                } else {

                    mid = *it2;

                    it2++;

                }

            } else if (it1 != nums1.end()) {

                mid = *it1;

                it1++;

            } else if (it2 != nums2.end()) {

                mid = *it2;

                it2++;

            }

            half--;

        }

        if (totalSize % 2 == 0) {

            return (double)(preMid + mid) / 2;

        } else {

            return mid;

        }

    }

};

當然也可以參考網路上的思路
https://www.youtube.com/watch?v=KB9IcSCDQ9k