【寻找两个正序数组的中位数LeetCode-4】

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    length1, length2 := len(nums1), len(nums2)
    // 注意，这里是向下取整
    mid := (length1 + length2) / 2

    // 区分一下奇数与偶数，奇数为mid+1，偶数为mid/mid+1
    // 奇数为2n+1个，mid=n,这样下一个就是中位数
    // 偶数为2n个，mid=n，所以处理一下，让mid=n-1，这样接下来两个就是中位数
    var isOdd bool
    if (length1 + length2) % 2 == 1 {
        isOdd = true
    } else {
        mid =  mid - 1
    }
    
    var i1, i2 int
    // 移动两个索引i1与i2，找到最小的mid个
    // 关键是注意两个边界情况的判定
    for mid > 0 {
        if i1 >= len(nums1) {
            i2++
        } else if i2 >= len(nums2) {
            i1++
        } else if nums1[i1] > nums2[i2] {
            i2++
        } else {
            i1++
        }
        
        mid--
    }

    // 找到mid后下一个
    var n1 int
    if i1 >= len(nums1) {
        n1 = nums2[i2]
        i2++
    } else if i2 >= len(nums2) {
        n1 = nums1[i1]
        i1++
    } else if nums1[i1] > nums2[i2] {
        n1 = nums2[i2]
        i2++
    } else {
        n1 = nums1[i1]
        i1++
    }

    // 奇数直接返回结果
    if isOdd {
        return float64(n1)
    }

    // 偶数找到再下一个，再返回
    var n2 int
    if i1 >= len(nums1) {
        n2 = nums2[i2]
    } else if i2 >= len(nums2) {
        n2 = nums1[i1]
    } else if nums1[i1] > nums2[i2] {
        n2 = nums2[i2]
    } else {
        n2 = nums1[i1]
    }

    return float64(n1 + n2) / 2
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    // Go里面不支持对 []int 直接进行排序，必须通过 sort.IntSlice 做一次转化
    var intSlice sort.IntSlice
    intSlice = append(intSlice, nums1...)
    intSlice = append(intSlice, nums2...)

    sort.Sort(intSlice)
    if len(intSlice) % 2 == 1 {
        // 注意这里的索引，切勿再+1
        return float64(intSlice[len(intSlice) / 2])
    }
    return float64(intSlice[len(intSlice) / 2 - 1] + intSlice[len(intSlice) / 2 ]) / 2
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    length1, length2 := len(nums1), len(nums2)
    // 奇数可以一步计算得出
    if (length1 + length2) % 2 == 1 {
        return findKthSortedArrays(nums1, nums2, (length1 + length2) / 2 + 1)
    }
    // 偶数的拆分为两个子问题
    return (findKthSortedArrays(nums1, nums2, (length1 + length2) / 2) +
        findKthSortedArrays(nums1, nums2, (length1 + length2) / 2 + 1)) / 2
}

func findKthSortedArrays(nums1 []int, nums2 []int, k int) float64 {
    length1, length2 := len(nums1), len(nums2)
    // 技巧1：保证nums1比nums2长，能减少下面很多条件的判断
    if length1 < length2 {
        return findKthSortedArrays(nums2, nums1, k)
    } else if length2 == 0 {
        return float64(nums1[k - 1])
    } else if k == 1 {
        if nums1[0] > nums2[0] {
            return float64(nums2[0])
        }
        return float64(nums1[0])
    }

    // 我们要保证i1和i2都要小于k，否则下面很难递归
    i2 := k / 2
    if i2 > length2 {
      i2 = length2
    }
    i1 := k - i2

    // 递归的核心思路
    if nums1[i1 - 1] < nums2[i2 - 1] {
        return findKthSortedArrays(nums1[i1:], nums2, k - i1)
    } else if (nums1[i1 - 1] > nums2[i2 - 1]) {
        return findKthSortedArrays(nums1, nums2[i2:], k - i2)
    }
    return float64(nums1[i1 - 1])
}