The following three problems are interlinked, and the solution of the previous problem can be used to solve the next problem. Solve problem 1 first, then solve problem 2 based on problem 1, and then solve problem 3 based on problem 2.

  1. NC36 finds the upper median in two sorted arrays of equal length
  2. CD82 finds the KTH smallest number in both sorted arrays
  3. Leetcode 4. Find the median of two positive ordinal groups

Question 1

There’s a couple of ways to do it

  • Put them all together, sort them all
  • Follow the merge sort “one merge” process, but do not actually merge, just move the pointer, find the upper median and return
  • binary
  • Divide the array

The following specific analysis of the last “partition array” solution method. Given that the two arrays are equally long and ordered, let’s analyze a number of possible situations,

  • The length of the array is 0
    • Does not conform to the input data limits given in the problem
  • The length of the array is 1
    • The smaller value is the upper median
  • The length of the array is greater than or equal to 2
    • The values are equal
      • The length of the array is an odd number Set an array for a =,1,2,3,4 [0], another for a ‘= [0, 1’, 2 ‘, 3 ‘, 4 ‘]. Note that the numbers in the array are elements’ indexes (starting from 0), not concrete values. “Equal median”, then 2==2 prime. Obviously, the upper median is 2 (or 2′).
      • Let one array a=[0,1,2,3] and another array A ‘=[0′,1′,2′,3′]. “Equal median”, then 1==1 prime. Obviously, the upper median is 1 (or 1’).
    • One median is greater than the other
      • The length of the array is odd
      • The length of the array is even
    • One median is less than the other (the situation is similar)
      • The length of the array is odd
      • The length of the array is even

Question 2

Ideas:

Question 3

Idea: According to the nature of ordered arrays, constantly discard the interval where the required data does not exist. This is indeed a difficult problem, requiring careful analysis of multiple situations. The best way is to work it out on paper.

// the entry function
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    l1 := len(nums1)
    l2 := len(nums2)
    if l1 == 0 && l2 == 0 {
        panic("nums1 and nums2 are all empty")}if l1 == 0 {
        return getMedian(nums2)
    }
    if l2 == 0 {
        return getMedian(nums1)
    }
    // l1 > 0 && l2 > 0
    l := l1+l2
    if l&1! =0 {
        return float64(getKthSmallest(nums1, nums2, l>>1+1))}return (float64(getKthSmallest(nums1, nums2, l>>1)) +float64(getKthSmallest(nums1, nums2, l>>1+1))) /2
}

// Find the KTH smallest of two ordered arrays
// k >= 1 && k <= len(a1)+len(a2)
func getKthSmallest(a1, a2 []int, k int) int {
    var (
        l1 = len(a1)
        l2 = len(a2)
    )
    if k < 1 || k > l1+l2 {
        panic("k is invalid")}var (
        sl = l1 // The length of the short array
        sa = a1 / / short array
        ll = l2 // The length of the long array
        la = a2 / / array
    )
    if l1 > l2 {
        sl = l2
        sa = a2
        ll = l1
        la = a1
    }
    if k <= sl {
        return getUpMedian(a1[:k], a2[:k])
    }
    if k > ll {
        li := k-sl- 1 // The index of the long array
        if la[li] >= sa[sl- 1] {
            return la[li]
        }
        si := k-ll- 1
        if sa[si] >= la[ll- 1] {
            return sa[si]
        }
        return getUpMedian(sa[si+1:], la[li+1:)}// k > sl && k <= ll
    li := k-sl- 1 // Long array index
    if la[li] >= sa[sl- 1] {
        return la[li]
    }
    if la[k- 1] <= sa[0] {
        return la[k- 1]}return getUpMedian(sa, la[li+1:k])
}

// Find the upper median of two ordered arrays of equal length
func getUpMedian(a1, a2 []int) int {
    var (
        l1 = len(a1)
        l2 = len(a2)
    )
    ifl1 ! = l2 {panic("len(a1) ! = len(a2)")}var (
        b1 int
        e1 = l1- 1
        b2 int
        e2 = l2- 1
    )
    for b1 < e1 && b2 < e2 {
        m1 := b1+(e1-b1)>>1
        m2 := b2+(e2-b2)>>1
        l := e1-b1+1
        if a1[m1] == a2[m2] {
            return a1[m1]
        }
        if a1[m1] > a2[m2] {
            if l&1! =0 {
                e1 = m1
                b2 = m2
            } else {
                e1 = m1
                b2 = m2+1}}else {
            if l&1! =0 {
                b1 = m1
                e2 = m2
            } else {
                b1 = m1+1
                e2 = m2
            }
        }
    }
    return min(a1[b1], a2[b2])
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// Compute the median of an ordered array
func getMedian(nums []int) float64  {
    l := len(nums)
    if l == 0 {
        panic("nums is empty")}if l&1! =0 {
        return float64(nums[l>>1])}return (float64(nums[l>>1- 1]) +float64(nums[l>>1) /])2
}
Copy the code

Time complexity O (log (min (m, n))) O (log (min (m, n))) O (log (min (m, n))), space complexity O (1) O (1) O (1).