Leetcode Top100 Challenge, find the median of two positive ordinal groups (2/100)

This is the 9th day of my participation in Gwen Challenge

Topic describes

Find the median of two positive ordinal groups

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. Leetcode-cn.com/problems/me…

/ / sample 1Enter: nums1 = [1.3], nums2 = [2] output:2.00000Merge array = [1.2.3], median2
/ / sample 2Enter: nums1 = [1.2], nums2 = [3.4] output:2.50000Merge array = [1.2.3.4], median (2 + 3) / 2 = 2.5Output:1.2]
/ / sample 3Enter: nums1 = [0.0], nums2 = [0.0] output:0.00000

Copy the code

The label

Violence enumeration of two Pointers

Analysis of the problem solving

Enumeration of violence

Straight ahead, two ordered arrays, find the median. Just turn it into an ordered array.

Then take the median, which = data [data length / 2] when the number of data in a set is odd.

Such as median [1, 2, 3, 4, 5] [1, 2, 3, 4, 5] [math.h floor (5/2)] = > [1, 2, 3, 4, 5] [2] = > 3

When the number of data in a set is even, (median = data [(data length / 2)] + data [(data length / 2-1)) / 2.

Such as median [6] ([6] [6/2] + [6] [6/2 + 1]) / 2 = > (4 + 3) / 2 = > 3.5

Go straight to the code.

function findMedianSortedArrays(nums1: number[], nums2: number[]) :number {
    // Get the sum of two array lengths
    const n: number  = nums1.length + nums2.length
    // Merge and sort the two arrays from smallest to largest
    const nums: number [] = [...nums1, ...nums2].sort((a, b) = > b - a)
    // If the length of the merged array is even, either add the two middle numbers and divide by 2, or use the middle number
    if(n % 2= = =0 ) return (nums[n / 2] + nums[n / 2 - 1) /2
    else return nums[Math.floor(n / 2)]};Copy the code

2. Double pointer

Speed pointer is also a double pointer, but two Pointers from the same side began to iterate through group, the two Pointers, respectively defined as pointer quickly (fast) and slow pointer (missile), two Pointers to move a different strategy, until two pointer values are equal () or other special conditions, such as fast growth two at a time, a missile every time growth.

Because we know that the two arrays passed in are ordered, we can reduce the number of passes by using double Pointers.

Suppose we pass array a as [1,3] and array b as [2,4,5].

The number of times we iterate is zeroMath.floor((a.length + b.length) /2Pointer A to array A [0] the subscript1Pointer B to b array [0] the subscript2The first time1   3  
*
2   4   5* If pointer A does not run through array A and the value of pointer A is less than that of pointer B, save the value of pointer A as the current value and move, otherwise let pointer B go. We see that pointer A does not complete array A and is less than pointer to subscript [0] value for2Pointer B, continue to go pointer A. The current value is zero1Let's do it a second time1   3  
    *
2   4   5* At this point we continue to judge pointing to subscripts [1] value for3Pointer a, which is already better than pointer to subscript [0] value for2If pointer B is large, let pointer B continue to run. The current value is zero2Let's do it a third time1   3  
    *
2   4   5* Same logic,3than4Small and not finished, go A. The current value is zero3

[1.2.3.4.5] => Median3 
Copy the code

function findMedianSortedArrays(nums1: number[], nums2: number[]) :number {

    const [n1, n2] = [nums1.length, nums2.length]
    const len = n1 + n2  // Get the total length to traverse
    let [preValue, curValue] = [-1, -1] //curValue is the current value of the pointer, and preValue is needed to solve the even-length array median
    let [point1, point2] = [0.0] // pointer a, b

    // Only half of the loop
    for(let i =0; i<= Math.floor(len  /2); i++) {
        // Get the last value
        preValue = curValue
        // If a does not complete array A and b does not complete array B or a is not as large as B, let a move; otherwise, let B move.
        if(point1 < n1 && (point2 >= n2 || nums1[point1] < nums2[point2])) {
            curValue = nums1[point1]
            point1++
        }
        else {
            curValue = nums2[point2]
            point2++
        }
    }


    if(len % 2= = =0) return (preValue + curValue) / 2
    else return curValue
};
Copy the code

The last

Not pigeon from today, every day an algorithm problem and publish articles, first want to solve the problem group for Top100, the second topic finished work!!