[Leetcode]4.Median of Two Sorted Arrays

川长思鸟来 2022-06-18 05:08 154阅读 0赞

> This question requires us to find the median from 2 sorted arrays. The 2 arrays are sorted and of size m and n, respectively.  
> For example, for `[1,3]` and `[2,4]`, the median is `2 + 3 / 2 = 2.50`.  
> The algorithm should run in `O(log(m + n))` time.

## Method 1: ##

### Analysis1: ###

In order to solve this question, we need to first understand what a **median** is. A **median** is the middle value of a dataset.  
Since we have 2 seperately sorted array in this question, to find the middle value is somewhat complicated. However, keep in mind that we do not care about the actual value of the numbers, what we want is the middle point from the combination of 2 arrays. In other words, we are looking for the middle index of the 2 arrays. Thus approach like `binary search` could be employed.  
Based on the fact that the 2 arrays are sorted seperatedly, we could try to get the submedian of the 2 arrays in each round. Than compare them. And the basic idea is that the left half of the array with a smaller submedian can never contains the common median.

if (mid1 < mid2) keep nums1.right + nums2
    else keep nums1 + nums2.right

Thus a `O(log(m + n))` is like following:

public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            // Deal with invalid corner case. 
            if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return 0.0;
    
            int m = nums1.length, n = nums2.length;
            int l = (m + n + 1) / 2; //left half of the combined median
            int r = (m + n + 2) / 2; //right half of the combined median
    
            // If the nums1.length + nums2.length is odd, the 2 function will return the same number
            // Else if nums1.length + nums2.length is even, the 2 function will return the left number and right number that make up a median
            return (getKth(nums1, 0, nums2, 0, l) + getKth(nums1, 0, nums2, 0, r)) / 2.0;
        }
    
        private double getKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
            // This function finds the Kth element in nums1 + nums2
    
            // If nums1 is exhausted, return kth number in nums2
            if (start1 > nums1.length - 1) return nums2[start2 + k - 1];
    
            // If nums2 is exhausted, return kth number in nums1
            if (start2 > nums2.length - 1) return nums1[start1 + k - 1];
    
            // If k == 1, return the first number
            // Since nums1 and nums2 is sorted, the smaller one among the start point of nums1 and nums2 is the first one
            if (k == 1) return Math.min(nums1[start1], nums2[start2]);
    
            int mid1 = Integer.MAX_VALUE;
            int mid2 = Integer.MAX_VALUE;
            if (start1 + k / 2 - 1 < nums1.length) mid1 = nums1[start1 + k / 2 - 1];
            if (start2 + k / 2 - 1 < nums2.length) mid2 = nums2[start2 + k / 2 - 1];
    
            // Throw away half of the array from nums1 or nums2. And cut k in half
            if (mid1 < mid2) {
                return getKth(nums1, start1 + k / 2, nums2, start2, k - k / 2); //nums1.right + nums2
            } else {
                return getKth(nums1, start1, nums2, start2 + k / 2, k - k / 2); //nums1 + nums2.right
            }
        }
    }

--------------------

## Method2: ##

### Analysis2: ###

Basic ides is like the above one, but the thoughts is like following:  
find the kth element int the two sorted arrays  
let us say: A\[aMid\] <= B\[bMid\], x: mid len of a, y: mid len of b, then wen can know  
(1) there will be at least (x + 1 + y) elements before bMid  
(2) there will be at least (m - x - 1 + n - y) = m + n - (x + y +1) elements after aMid  
therefore  
if k <= x + y + 1, find the kth element in a and b, but unconsidering bMid and its suffix  
if k > x + y + 1, find the k - (x + 1) th element in a and b, but unconsidering aMid and its prefix

public class Solution{
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length, n = nums2.length;
            int l = (m + n + 1) / 2;
            int r = (m + n + 2) / 2;
            return (getKth(nums1, 0, m - 1, nums2, 0, n - 1, l) + getKth(nums1, 0, m - 1, nums2, 0, n - 1, r)) / 2.0;
        }
    
        private double getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
            if (start1 > end1) return nums2[start2 + k - 1];
            if (start2 > end2) return nums1[start1 + k - 1];
            if (k == 1) return Math.min(nums1[start1], nums2[start2]);
    
            int mid1 = start1 + (end1 - start1) / 2;
            int mid2 = start2 + (end2 - start2) / 2;
    
            if (nums1[mid1] <= nums2[mid2]) {
                if (k <= (mid1 - start1) + (mid2 - start2) + 1) {
                    return getKth(nums1, start1, end1, nums2, start2, mid2 - 1, k);
                } 
                else {
                    return getKth(nums1, mid1 + 1, end1, nums2, start2, end2, k - (mid1 - start1) - 1);
                }
            } 
            else {
                // if (k <= (mid1 - start1) + (mid2 - start2) + 1) {
        
                //     return getKth(nums1, start1, mid1 - 1, nums2, start2, end2, k);
                // }
                // else {
        
                //     return getKth(nums1, start1, end1, nums2, mid2 + 1, end2, k - (mid2 - start2) - 1);
                // }
    
                return getKth(nums2, start2, end2, nums1, start1, end1, k);
            }
        }
    }

--------------------

## Method3: ##

### Analysis3: ###

See [here][]. Too long and complicated. Don’t wnat to dig it too much.

[here]: https://discuss.leetcode.com/topic/4996/share-my-o-log-min-m-n-solution-with-explanation/2