LeeCode QUESTION No.04 -- "Find the Median of Two Ordered Arrays"_A Little Classroom (Multishore College)

Finding the Median of Two Ordered Arrays

Topic: Finding the Median of Two Ordered Arrays

Description: Given two ordered arrays of M and n, nums1 and nums2. Please find the median of these two ordered arrays and require the time complexity of the algorithm to be O (log (m + n). You can assume that nums1 and nums2 are not empty at the same time.

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

analysis

After seeing the title, the first feeling is that this is not merger sort? So you can write the following code very quickly:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if(nums1 == null || nums1.length == 0){
        return findMedianSortedArrays(nums2);
    }
    if(nums2 == null || nums2.length == 0){
        return findMedianSortedArrays(nums1);
    }

    int[] nums = new int[nums1.length+nums2.length];
    int index1 = 0;
    int index2 = 0;
    int index = 0;
    while (index1<nums1.length && index2<nums2.length) {
        if(nums1[index1]<nums2[index2]){
            nums[index++] = nums1[index1++];
        }else{
            nums[index++] = nums2[index2++];
        }
    }

    while(index1<nums1.length){
        nums[index++] = nums1[index1++];
    }

    while(index2<nums2.length){
        nums[index++] = nums2[index2++];
    }

    return findMedianSortedArrays(nums);
}

private double findMedianSortedArrays(int[] nums){
    int len = nums.length;
    if(len%2==1){
        return nums[len/2];
    }else{
        return (nums[len/2-1]+nums[len/2])/2.0;
    }
}

However, the merging process requires O(max(m, n)) time complexity, which is inconsistent with the requirements of the title. To achieve the O (log (m + n) level of time complexity, you must use a similar approach to half-look-up. Using merge sort will combine two numbers into an ordered array, and then find its intermediate value. Is it possible to find this value without sorting?

Let's assume that the median of two arrays is k, where k=(m+n)/2. If we find this value, we will find the median, so we can convert the problem into finding the largest number of K in two arrays.

In order to get the results more quickly, we use the dichotomy method for shorter arrays. By using the property that there must be k-1 number before the larger number of k, we can determine the position of longer arrays that should be divided. The following is the following:

Because the value of the largest K must be bigger than that of the largest a, and also bigger than that of the largest b, we can discard all the values before the smaller A and b, and thus convert the value of the largest K in the number of m+n into the value of the largest K-a (or k-b) in the number of m+n-a (or m+n-b). For example, if the value at a is smaller than that at b, we will discard all the values before a and make the next comparison as follows:

The procedure code for finding the maximum k is as follows:

/**
 * Get the value of the largest k
 * 
 * @param nums1
 * @param nums2
 * @param len1 Length of Array 1
 * @param len2 Length of Array 2
 * @param start1 Starting Point of Array 1 Effective
 * @param start2 Array 2 is a valid starting point
 * @return The value of the largest k
 */
private static int findMedianSortedArraysOptimize(int[] nums1, int[] nums2, int len1, int len2, int start1, int start2, int k){
    if(len1 > len2){
        return findMedianSortedArraysOptimize(nums2, nums1, len2, len1, start2, start1, k);
    }
    if(len1 == 0){
        return nums2[start2 + k - 1];
    }

    if(k == 1){
        return Math.min(nums1[start1], nums2[start2]);
    }

    int ignore1 = Math.min(k/2, len1);
    int ignore2 = k - ignore1;
    if(nums1[start1 + ignore1 - 1] < nums2[start2 + ignore2 - 1]){
        // Discard the value before the comparison bit of array 1
        return findMedianSortedArraysOptimize(nums1, nums2, len1-ignore1, len2, start1+ignore1, start2, k-ignore1);
    }else if(nums1[start1 + ignore1 - 1] > nums2[start2 + ignore2 - 1]){
        // Discard the value before the comparison bit of array 2
        return findMedianSortedArraysOptimize(nums1, nums2, len1, len2-ignore2,  start1, start2+ignore2, k-ignore2);
    }else{
        // The value of the largest k is found.
        return nums1[start1+ignore1-1];
    }
}

Find the value of the largest k, and then find the median is very simple, the call code is as follows:

public double findMedianSortedArraysOptimize(int[] nums1, int[] nums2) {
    int len1 = nums1.length;
    int len2 = nums2.length;
    int k = (len1+len2)/2;
    if((len1+len2)%2 == 1){
        return findMedianSortedArraysOptimize(nums1, nums2, len1, len2, 0, 0, k+1);
    }else{
        return (findMedianSortedArraysOptimize(nums1, nums2, len1, len2, 0, 0, k) + findMedianSortedArraysOptimize(nums1, nums2, len1, len2, 0, 0, k+1))/2.0;
    }
}

summary

This topic tells us that there are many solutions to the same problem. Sometimes it is better to transform the problem into other problems.

Next topic announcement

Topic: Longest Palindrome Substring

Description: Given a string s, find the longest palindrome substring in S. You can assume that the maximum length of S is 1000.

Example:

  • Input: "babad"
  • Output: "bab"
  • Note: "aba" is also an effective answer.

See the source code in the code directory.

Thank you for seeing it. If you can help me, please give me a compliment.

More experience and technology are welcome to come and learn together. A Little Classroom - Online Learning Platform for Dreams http://www.yidiankt.com/

[Pay attention to the public number and reply to "1" for free - [java Core Knowledge Points]

QQ discussion group: 616683098

QQ: 3184402434

Students who want to study in depth can study and discuss with QQ ~and have a full set of resources to share, experience to explore, wait for you!

Tags: Programming Java

Posted on Tue, 10 Sep 2019 20:58:26 -0700 by chrisdarby