“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

The question to describe

Given two positive-ordered (from small to large) arrays of size m and n, nums1 and nums2. Please find and return the median of the two positive ordinal groups.

Example 1:

Input: nums1 = [1,3], nums2 = [2] output: 2.00000 explanation: merge array = [1,2,3], median 2

Example 2:

Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5

Analysis of ideas:

We all know that the median is the number in the middle of an ordered sequence, so we divide the first array into two parts, the smaller part on the left and the larger part, and the other array does the same thing to move the middle separator. It’s going to come down in turn.

  • The sum of the number of smaller parts of two arrays == the sum of the number of larger parts of two arrays
  • The number of the smaller part <= the number of the larger part
  • When both conditions are met, the median of the two arrays is generated between the two partitions
nums1 = [1.2];
nums2 = [3.4];
var compare = function (x, y) {// Compare functions
    if (x < y) {
        return -1;
    } else if (x > y) {
        return 1; }}var findMedianSortedArrays = function(nums1, nums2) {
    var data = nums1.concat(nums2);
    var mid; 
    data.sort(compare); 
    if (data.length%2= =0){
        mid = (data[data.length/2-1]+data[data.length/2) /2
    }
    if (data.length%2! =0){
        mid = data[(data.length-1) /2]}return mid;
};
findMedianSortedArrays(nums1, nums2);
Copy the code

Binary processing optimization

Move by position to binary search move to find separation points faster.

 let findMedianSortedArrays = (nums1, nums2) = > {
    
    if (nums1.length > nums2.length) { // to ensure m<=n
        [nums1,nums2] = [nums2,nums1]
    }
    let m = nums1.length;
    let n = nums2.length;
    let l = 0, r = m, halfLen = Math.floor((m + n + 1) / 2);
    console.log('halfLen',halfLen)
    while (l <= r) {
        let i = Math.ceil((r + l) / 2);
        let j = halfLen - i;
        if (i < r && nums2[j-1] > nums1[i]){
            l = l + 1; // i is too small
        }
        else if (i > l && nums1[i-1] > nums2[j]) {
            r = r - 1; // i is too big
        }
        else { // i is perfect
            let maxLeft = 0;
            if (i == 0) { maxLeft = nums2[j-1]; }
            else if (j == 0) { maxLeft = nums1[i-1]; }
            else { maxLeft = Math.max(nums1[i-1], nums2[j-1]); }
            if ( (m + n) % 2= =1 ) { return maxLeft; }

            let minRight = 0;
            // Critical value indicates that nums1 before m is less than nums2
            if (i == m) { minRight = nums2[j]; }
            // Critical indicates that nums2 before n is less than nums1
            else if (j == n) { minRight = nums1[i]; }
            
            else { minRight = Math.min(nums2[j], nums1[i]); }
            console.log(minRight,maxLeft)
            return (maxLeft + minRight) / 2.0; }}return 0.0; 
}
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤