Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

  1. The largest string without repeating characters – difficulty difficult

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.

The time complexity of the algorithm should be order log m plus n.

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

Tip:

nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106

Ii. Topic and Idea Analysis:

Although the problem is labeled difficult, it’s actually not difficult in terms of solving it. Merge the array and fetch the median of the array.

Concat () can be used to merge arrays, and the median can be judged by the method of taking the remainder. If the remainder is 1, it indicates that the array is odd, and the value corresponding to the median of the subscript can be directly taken; if the remainder is 0, it indicates that the array is even, and the average value corresponding to the two medians of the subscript should be taken.

Sort (a,b)=>{a-b}); sort(a,b)=>{a-b});

Speaking of which, there is another important thing that I forgot from the problem, which is that the algorithm should be order log (m+n)). What does that mean? There’s a picture online that you can look at:

As we can see, when the array length increases, the time required does not increase exponentially, but gradually slows down. As we can see from the above solution idea, our calculation time is not greatly affected by the array length, but by the log(m+n) curve.

Iii. Code:

The code implementation is as follows:

var findMedianSortedArrays = function(nums1, nums2) {
    let arr = nums1.concat(nums2).sort((a, b) => a - b)
    let length = arr.length
    let i = 0
    let res = 0
    console.log(arr,length,i,res)
    if(length % 2 == 1){
        i = --length/2
        res = arr[i]
    }else{
        i = length/2
        res = (arr[i]+arr[i-1])/2
    }
    return res
};
Copy the code

Iv. Summary:

The process of solving the problem should be careful, a little mistake will lead to the wrong answer, about the big O notation, but also to review the mathematical knowledge, the most important or ideas.

Come on!