--

leetcode 004: Median of Two Sorted Arrays

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

---

---

problem:

---

  
There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

---

---

start code (c++)

---

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        
    }
};

---

---

solution 1:

我的思路：
不失一般性，我们可以认为 vec a1 较短，长度为 m1，vec a2 较长，长度为 m2
我们的目标是，找到一个 median 的数，这个数字把 a1 分成两组，我们称为 a1_left, a1_right, 使得所有的 a1_left <= median <= a1_right
同时，median 也把 a2 分成两组，我们称之为 a2_left, a2_right, 使得 a2_left <= median <= a2_right
并且也要满足，a1_left.size() + a2_left.size() == a1_right.size() + a2_right.size()

如何找到这个 median 呢？
我们先从 size 入手，先找一个 a1 和 a2 的左右分组，使得 a1_left.size() + a2_left.size() == a1_right.size() + a2_right.size()

1. 计算 a1 的中位数，a1_median, 它把 a1 分成两组，a1_left, a1_right, 两边大小相等。
2. 计算 a2 的中位数，a2_median, 它把 a2 分成两组，a2_left, a2_right, 两边大小相等。

如果，很巧的，a1_median 和 a2_median 相等，那么我们的问题已经解决了。

如果不巧的，两者不相等，那么不失一般性，假设 a1_median < a2_median,
我们要做的事情是，在 a1 里面，把这个 a1_median 适当右移，使之增大。
同时在 a2 里面，把这个 a2_median 适当左移，使之减小。
我们在 a1 和 a2 里面移动的数目应该是相等的，这样才能始终保证，a1_left.size() + a2_left.size() == a1_right.size() + a2_right.size()
在某个恰当的移动的数目 (我们称之为 x) 的时候，我们能够使得 a1_median == a2_median

那么问题现在变成为：
我们怎么找到这个 x？
x 可以选择的大小为 0 到 a1_size() / 2
我们用两分法，就可以很快找到这个恰当的 x 了。 耗费的时间，应该正比于 lg(a1_size) = lg(m1) = lg(min(m1,m2))

在写代码的时候，要非常小心边界情况，并且考虑到数组长度为偶数和奇数的不同情况。
以下的代码可能是编译不通过的，但是大致意思是这样的

---

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        # nums1 always longer than nums2
        if len(nums1) == 1:
            if len(nums2) % 2 == 0:
                return nums2[len(nums2) / 2] /2 + nums2[len(nums2)/2 -1] /2 
        l1 = 0
        h1 = len(nums1) -1
        l2 = len(nums2) / 2 - len(nums1) / 2
        h2 = len(nums2) / 2 + len(nums1) / 2
        m1 = (l1 + h1) / 2
        m2 = (l2 + h2) / 2
        while (h1 > l1):
            m1 = (l1 + h1) / 2
            m2 = (l2 + h2) / 2
            if nums1[m1] == nums2[m2]:
                return nums1[m1]
            elif nums1[m1] < nums2[m2]:
                l1 = m1 + 1
                h2 = m2 - 1
            else:
                h1 = m1 -1
                l2 = m2 + 1
        return (nums1[m1] + nums2[m2]) / 2
        

---