2021-06-29：在两个都有序的数组中找整体第K小的数。

福大大架构师每日一题

发布于 2021-08-05 08:13:53

50000

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2021-06-29：在两个都有序的数组中找整体第K小的数。

福大大答案2021-06-29：

1.A和B长度不等的时候，需要把A和B的长度变成相等。

A是短数组，B是长数组。

第k小的数，k从1开始。

k<=短，都取前k个数，变成等长。

短<k<=长，长取中，长扣1。

长<k<=和,两个数组都取后变成等长，两个数组都需要扣掉1个元素，小被干，都需要扣掉左边。

2.A和B长度相等的时候。分长度是偶数和长度是奇数两种情况。都是求中位数。

2.1.A和B长度相等，并且长度是偶数。

A=[A1,A2,A3,A4]

B=[B1,B2,B3,B4]

当A2==B2时，取A2。

当A2>B2时，B1、B2、A3、A4去掉。递归。

2.2.A和B长度相等，并且长度是奇数。

A=[A1,A2,A3,A4,A5]

B=[B1,B2,B3,B4,B5]

当A3==B3时，取A3。

当A3>B3时，B1、B2、A3、A4、A5去掉。当A2<=B3时，取B3；否则去掉B3，递归。

时间复杂度是O(log(min(M,N)))。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    arr1 := []int{1, 3}
    arr2 := []int{2}
    ret := findMedianSortedArrays(arr1, arr2)
    fmt.Println(ret)
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    size := len(nums1) + len(nums2)
    even := (size & 1) == 0
    if len(nums1) != 0 && len(nums2) != 0 {
        if even {
            return float64(findKthNum(nums1, nums2, size/2)+findKthNum(nums1, nums2, size/2+1)) / 2.0
        } else {
            return float64(findKthNum(nums1, nums2, size/2+1))
        }
    } else if len(nums1) != 0 {
        if even {
            return float64((nums1[(size-1)/2] + nums1[size/2]) / 2)
        } else {
            return float64(nums1[size/2])
        }
    } else if len(nums2) != 0 {
        if even {
            return float64((nums2[(size-1)/2] + nums2[size/2]) / 2)
        } else {
            return float64(nums2[size/2])
        }
    } else {
        return 0
    }
}

// 进阶问题 : 在两个都有序的数组中，找整体第K小的数
// 可以做到O(log(Min(M,N)))
func findKthNum(arr1 []int, arr2 []int, kth int) int {
    longs := twoSelectOne(len(arr1) >= len(arr2), arr1, arr2)
    shorts := twoSelectOne(len(arr1) < len(arr2), arr1, arr2)
    l := len(longs)
    s := len(shorts)
    if kth <= s { // 1)
        return getUpMedian(shorts, 0, kth-1, longs, 0, kth-1)
    }
    if kth > l { // 3)
        if shorts[kth-l-1] >= longs[l-1] {
            return shorts[kth-l-1]
        }
        if longs[kth-s-1] >= shorts[s-1] {
            return longs[kth-s-1]
        }
        return getUpMedian(shorts, kth-l, s-1, longs, kth-s, l-1)
    }
    // 2)  s < k <= l
    if longs[kth-s-1] >= shorts[s-1] {
        return longs[kth-s-1]
    }
    return getUpMedian(shorts, 0, s-1, longs, kth-s, kth-1)
}

// A[s1...e1]
// B[s2...e2]
// 一定等长！
// 返回整体的，上中位数！8（4） 10（5） 12（6）
func getUpMedian(A []int, s1 int, e1 int, B []int, s2 int, e2 int) int {
    mid1 := 0
    mid2 := 0
    for s1 < e1 {
        // mid1 = s1 + (e1 - s1) >> 1
        mid1 = (s1 + e1) / 2
        mid2 = (s2 + e2) / 2
        if A[mid1] == B[mid2] {
            return A[mid1]
        }
        // 两个中点一定不等！
        if ((e1 - s1 + 1) & 1) == 1 { // 奇数长度
            if A[mid1] > B[mid2] {
                if B[mid2] >= A[mid1-1] {
                    return B[mid2]
                }
                e1 = mid1 - 1
                s2 = mid2 + 1
            } else { // A[mid1] < B[mid2]
                if A[mid1] >= B[mid2-1] {
                    return A[mid1]
                }
                e2 = mid2 - 1
                s1 = mid1 + 1
            }
        } else { // 偶数长度
            if A[mid1] > B[mid2] {
                e1 = mid1
                s2 = mid2 + 1
            } else {
                e2 = mid2
                s1 = mid1 + 1
            }
        }
    }
    return getMin(A[s1], B[s2])
}

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

func twoSelectOne(c bool, a []int, b []int) []int {
    if c {
        return a
    } else {
        return b
    }
}