[LeetCode, 리트코드] Median of Two Sorted Arrays

1. 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.

두 정렬된 배열 nums1, nums2가 있고 각각의 사이즈는 m과 n이다.

두 정렬된 배열의 중앙값을 찾아라 시간복잡도는 O(log (m+n))이어야 된다. nums1과 nums2는 빈 배열이 아니라고 생각해도 좋다.

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

2. Solution

To solve the problem, understanding the nature of the median is very important. One of the characteristics of the median is that dividing a set into two sets, the set of lower elements, the set of higher elements. 

이 문제를 풀기 위해서는 중앙값의 성질에 대해 이해하는 것이 중요하다. 중앙값의 하나의 특징은 한 집합을 두 개의 각기 다른 집합으로 나눈다는 것이다. 작은 요소들의 집합과 큰 요소들의 집합으로.

Each array has elements included a lower set or higher set simultaneously like this. 

각 배열들은 작은 요소들의 집합에 속해있는 요소들이거나 큰 요소들의 집합에 속해있는 요소들을 동시에 가지고 있다.

          left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

left_part is the lower element set and right_part is the higher element set. Using this feature, we can deduce the following formula

left_part는 작은 요소들의 집합이고 right_part는 큰 요소들의 집합이다. 이 성질을 이용하여 다음 공식을 도출해 낼 수 있다.

1. $\text{len}(\text{left\_part})=\text{len}(\text{right\_part})$
2. $\max(\text{left\_part}) \leq \min(\text{right\_part})$

left_part's size and right_part's size are equal. There is no doubt. The second formula is obvious because left_part's elements are always less than the right_part's

left_part의 크기과 right_part의 크기가 같다. 이것은 자명하다. 두 번째 공식은 명백한데 왜냐하면 언제나 left_part들의 요소는 right_part의 요소보다 작기 때문이다.

Using more specific formula, above formula can be represented like this.

이걸 더 세세한 공식을 쓰면 다음과 같이 된다.

1. $i+j=m-i+n-j$ (or: $m - i + n - j + 1$)
   if $n \geq m$, we just need to set: $i = 0 \sim m, j = \frac{m + n + 1}{2} - i \\$

2. $\text{B}[j-1] \leq \text{A}[i]$ and $\text{A}[i-1] \leq \text{B}[j]$

It means

이것이 의미하는 것은

Searching $i$ in $[0, m]$, to find an object $i$ such that:

$\qquad \text{B}[j-1] \leq \text{A}[i]$ and $\ \text{A}[i-1] \leq \text{B}[j],$ where $j = \frac{m + n + 1}{2} - i$

3. What I solved

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if (m > n) { 
            nums1.swap(nums2);
            swap(m, n);
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && nums2[j-1] > nums1[i]){
                iMin = i + 1; 
            }
            else if (i > iMin && nums1[i-1] > nums2[j]) {
                iMax = i - 1; 
            }
            else {
                int maxLeft = 0;
                if (i == 0) { maxLeft = nums2[j-1]; }
                else if (j == 0) { maxLeft = nums1[i-1]; }
                else { maxLeft = max(nums1[i-1], nums2[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                int minRight = 0;
                if (i == m) { minRight = nums2[j]; }
                else if (j == n) { minRight = nums1[i]; }
                else { minRight = min(nums2[j], nums1[i]); }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
};

4. Best Solution

Same as above

위와 동일