This is the 19th day of my participation in the Gwen Challenge.More article challenges

For a better tomorrow, keep brushing LeetCode!

The title

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 2Copy the code

Example 2:

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

Example 3:

Input: nums1 = [0,0], nums2 = [0,0] output: 0.00000Copy the code

Example 4:

Input: nums1 = [], nums2 = [1] Output: 1.00000Copy the code

Example 5:

Input: nums1 = [2], nums2 = [] Output: 2.00000Copy the code

Tip:

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

Solution 1 – merge arrays

Their thinking

The brute force solution is to merge the two arrays and find the median.

code

func findMedianSortedArrays(nums1, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    nums := make([]int, m + n)
    var i, j int
    for k := 0; k < len(nums); k++ {
        if i < m && j < n {
            if nums1[i] < nums2[j] {
                nums[k] = nums1[i]
                i++ 
            }else {
                nums[k] = nums2[j]
                j++
            }
        }else if i < m {
            nums[k] = nums1[i]
            i++
        }else if j < n {
            nums[k] = nums2[j]
            j++
        }
    }

    if len(nums) % 2= =0 {
        return float64(nums[len(nums)/2] + nums[len(nums)/2- 1) /2
    }
    return float64(nums[len(nums)/2])}Copy the code

The execution result

Execution time: 16 ms beat 76.44% of users in all Go commits memory consumption: 5.7 MB beat 33.51% of users in all Go commitsCopy the code

Complexity analysis

  • Time complexity: O(m+n)O(m+n)O(m+n)
  • Space complexity: O(m+n)O(m+n)O(m+n)

Topic link

4. Find the median of two positive ordinal groups